# Next Permutation

### Problem statement

Given an array of integers, find the next lexicographically greater permutation of the array. If no greater permutation exists, arrange the array in ascending order. Perform the replacement in place using constant extra memory.

### Constraints

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

### Examples

a = \[1, 5, 8, 4, 7, 6, 5, 3, 1\]

Output = \[1, 5, 8, 5, 1, 3, 4, 6, 7\]

### Sudo Code

1. Find the first decreasing element from the end.
    
2. If no such element is found, reverse the array and return.
    
3. Find the next greater element to swap with.
    
4. Swap elements at indices i and j.
    
5. Reverse the sub-array from i+1 to the end.
    

### Dry Run

![](https://cdn.hashnode.com/res/hashnode/image/upload/v1689593460046/7a8a7eb1-345f-4e17-b86f-a159417db56d.jpeg align="center")

### Solution

```java
class Solution {
    void swap(int[] nums, int i, int j){
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

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

    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i;

        // Step 1 : Find the first decreasing element from the end.
        for(i=n-2;i>=0;i--){
            if(nums[i] < nums[i+1]){
                break;
            }
        }

        // Step 2. If no such element is found, reverse the array and return.
        if(i == -1){
            reverse(nums, 0, n-1);
            return;
        }

        // Step 3. Find the next greater element to swap with
        int j = n-1;
        while(nums[j] <= nums[i]){
            j--;
        }

        // Step 4. Swap elements at indices i and j
        swap(nums, i, j);

        // Step 5. Reverse the sub-array from i+1 to the end
        reverse(nums, i+1, n-1);
    }
}
```

### Time complexity Analysis

Time complexity: Linear - O(n)

Space complexity: Constant - O(1)

### Topics Covered

Two Pointers

### Companies

Flipkart, Amazon, Microsoft, Google, Qualcomm, Salesforce.

> This is my first blog, so please feel free to suggest anything and let's make this better together.
> 
> LinkedIn - [https://www.linkedin.com/in/shreyash-chavhan-609839163/](https://www.linkedin.com/in/shreyash-chavhan-609839163/)