# Next Permutation Leetcode Solution

Difficulty Level Medium
Array Goldmann Sachs Qualitrics tiktok Two PointersViews 8340

## Problem Statement

The Next Permutation LeetCode Solution – “Next Permutation” states that given an array of integers which is a permutation of first n natural numbers. We need to find the next lexicographically smallest permutation of the given array. The replacement must be in-place and use only constant extra space.

If the next lexicographically smallest permutation doesn’t exist for the given input array, return the array sorted in ascending order.

## Example:

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

Explanation:

• Next permutations are: [1, 3, 2], [2, 1, 3], [2, 3, 1], [3, 1, 2], [3, 2, 1].
• [1, 3, 2] is the lexicographically smallest next permutation of [1, 2, 3].
`Input:  nums = [3,2,1]`
`Output: [1,2,3]`

Explanation:

• Since the next lexicographically smallest permutation of the input array doesn’t exist, return [1, 2, 3] as the answer.

## Approach

### Idea:

1. The main idea to solve this problem is to use pointers.
2. The Brute force Solution is to generate all the permutations of the sorted input array. For every generated permutation, check whether this permutation is the lexicographic smallest next permutation of the input array or not. The Brute Force Solution will get a time limit exceeded verdict since time complexity will be n! where, n is the size of the input array.
3. From the end of the array, find the first index i such that arr[i] < arr[i+1].
4. Then, find the largest index j, such that arr[j] > arr[i] and j > i.
5. Swap the arr[i] and arr[j] and reverse the segment [i+1,n-1].
6. The resulting array formed from the above steps is the lexicographically smallest next permutation of the input array.

## Code

### Next Permutation Leetcode C++ Solution:

```class Solution {
public:
void nextPermutation(vector<int>& nums) {
int index = -1,n = nums.size();
for(int i=n-2;i>=0;i--){
if(nums[i]<nums[i+1]){
index = i;
break;
}
}
for(int i=n-1;i>index and index!=-1;i--){
if(nums[i]>nums[index]){
swap(nums[i],nums[index]);
break;
}
}
reverse(nums.begin()+index+1,nums.end());
}
};```

### Next Permutation Leetcode Java Solution:

```class Solution {
public void nextPermutation(int[] nums) {
int index = -1,n = nums.length;
for(int i=n-2;i>=0;i--){
if(nums[i]<nums[i+1]){
index = i;
break;
}
}
for(int i=n-1;i>=0 && index!=-1;i--){
if(nums[i]>nums[index]){
int temp = nums[index];
nums[index] = nums[i];
nums[i] = temp;
break;
}
}
int l = index + 1,r = n - 1;
while(l<r){
int temp = nums[l];
nums[l] = nums[r];
nums[r] = temp;
l++;r--;
}
}
}```

## Complexity Analysis for Next Permutation Leetcode Solution

### Time Complexity

The time complexity of the above code is O(N) since we traverse the entire input array once in the worst case where N = size of the input array.

### Space Complexity

The space complexity of the above code is O(1) since we’re using constant extra space.

Translate »