Problem Statement

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

Algorithm :

Start traversing from the right to left.

Make sure while traversing from the right to left, we are having an increasing order pattern.

If this increasing order pattern continues until we complete the traversal, then the given array is in its greatest permutation possible and there are no other next greater permutation. This time just reverse the whole array.

Otherwise, if at any of the index say i, the increasing order pattern is violated, just stop at that position and mark it as the violated index.

Now from that violated index i search for another index j to the right of i such that there is a number nums[j] which is just greater than nums[i].

After finding j, just swap the numbers at nums[i] and nums[j].

Now reverse the array from i + 1 to length - 1 where length is the size of array.

This will give us our next greater permuatation.

Code

class Solution {
    public void nextPermutation(int[] nums) {
        if (nums == null || nums.length <= 1) {
            return;
        }
        // we will be going from right to left and search for the index
        int violatingIncreasingOrder = -1;
        int length = nums.length;
        for (int i=length - 1; i>0; i--) {
            if (nums[i] > nums[i - 1]) {
                violatingIncreasingOrder = i - 1;
                break;
            }
        }
        // if already in greatest form, then just reverse the whole array
        if (violatingIncreasingOrder == -1) {
            reverse(nums, 0, length - 1);
            return;
        }
        int nextGreaterElementOfI = nums[violatingIncreasingOrder + 1];
        int violationNumber = nums[violatingIncreasingOrder];
        int nextGreaterIndex = violatingIncreasingOrder + 1;
        // find for the next greater index which is just greater than the violating number
        for (int i=violatingIncreasingOrder + 1; i<length; i++) {
            int currentNumber = nums[i];
            if (currentNumber > violationNumber && currentNumber <= nextGreaterElementOfI) {
                nextGreaterElementOfI = currentNumber;
                nextGreaterIndex = i;
            }
        }
        // reverse from the point of violation and the next greater element of that violation number
        swap(nums, violatingIncreasingOrder, nextGreaterIndex);
        reverse(nums, violatingIncreasingOrder + 1, length - 1);
    }

    private void reverse(int [] nums, int i, int j) {
        while (i < j) {
            swap(nums, i, j);
            i++;
            j--;
        }
    }

    private void swap(int [] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }
}