Next Permutation Leetcode Solution

Difficulty Level Medium
Frequently asked in Adobe Amazon Apple Bloomberg ByteDance DoorDash Facebook Google Microsoft Oracle PayU Rubrik Uber
Array Goldmann Sachs Qualitrics tiktok Two PointersViews 8841

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.

Reference: https://docs.microsoft.com/en-us/cpp/standard-library/algorithm-functions?view=msvc-170

Translate »