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

Solution

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/