Leetcode 31 : Next Permutation
Tags: java, programming, algorithms, tutorial
Published: 2021-11-07 05:49:10

## 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.


## Test Cases

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]
Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]
Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]
Example 4:

Input: nums = [1]
Output: [1]

## Constraints

1 <= nums.length <= 100
0 <= nums[i] <= 100

## Algorithm : 

1. Start traversing from the right to left.
2. Make sure while traversing from the right to left, we are having an increasing order pattern.
3. 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.
4. 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.
5. 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]`.
6. After finding `j`, just swap the numbers at `nums[i]` and `nums[j]`.
7. Now reverse the array from `i + 1` to `length - 1` where length is the size of array.
8. This will give us our next greater permuatation.

## Code 

```java
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;
    }
}
```

## Complexity : 

* Here we are traversing through the array from right to left one time and from the point of violation to right one time. So it will result in O(n) where n = size of array.

* We are not making use of any extra space, so space complexity is O(1).


## Github link :

{%github Rohithv07/LeetCode %}

{%github Rohithv07/LeetCodeTopInterviewQuestions %}