I was solving a question on leetcode with the description:

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. More formally, if all the permutations of the array are sorted in one container according to their lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted container. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

This is what I came up with in C :

    void nextPermutation(vector<int>& nums) {
        
            int index = -1, j = nums.size() - 1;

            for (int i = nums.size() - 1; i > 0; i--)
            {
                if(nums[i - 1] < nums[i])
                {
                    index = i - 1;
                    break;
                }
            }

            if(index == -1)
            {
                reverse(nums.begin(), nums.end());
                return;
            }

            for (int i = nums.size() - 1; i >= index   1; i--)
            {
                if(nums[i] > nums[index])
                {
                    j = i;
                }
                break;
            }

            swap(nums[index], nums[j]);
            reverse(nums.begin()   index   1, nums.end());

        }

Here I traversed the array from left to right and look for an element which is smaller than the element on its right(named it index), and then traversed it again looking for a number just bigger than the number before and swapped them and then reversed the array after index

This code works for the example cases but fails in a case where:

Input: [2,3,1]

MyOutput: [1,2,3]

Expected Output: [3,1,2]

I do not understand what I did wrong and everything should be working but its not.

CodePudding user response：

Your issue is that the break statement in second loop is outside the if block.

if (nums[i] > nums[index])
{
    j = i;
}
break;    // <--------- this should be inside if

Putting it inside, gives the correct result.

if (nums[i] > nums[index])
{
    j = i;
    break;
}

Demo: https://godbolt.org/z/147We9c4q