31. Next Permutation

#permutation #array #two-pointers

Problem

Next Permutation - LeetCodeLeetCode

Intuition

1. Longest Non-Increasing Suffix

The suffix represents a sub-sequence that is already at its maximum permutation rank. No rearrangement of these elements can increase the value.

• Key Point: Finding the first $A[i-1] < A[i]$ from the right identifies the rightmost possible position where an increase can occur.

2. The Boundary Case

If the suffix encompasses the entire array ($i=0$), the permutation is the absolute maximum. Reversing it yields the absolute minimum, completing the circular property of permutations.

3. Finding the Successor (Min-Max)

You seek the smallest value in the suffix that is strictly greater than the pivot ($A[i-1]$).

• Mathematical Invariant: Because the suffix is non-increasing, the first element found from the right that is $> A[i-1]$ is guaranteed to be the smallest such element. This maintains the "minimal change" requirement.

4. The Swap and Suffix Property

After swapping the pivot with its successor, the suffix remains non-increasing.

• Proof: The successor was the smallest element larger than the pivot. Replacing it with the pivot (which is smaller) does not break the descending order of the remaining elements.

5. Minimizing the Suffix

A non-increasing suffix is the "largest" version of that sequence. To make the entire number the "next" smallest possible, the suffix must be converted to the "smallest" version (non-decreasing).

• Optimization: Since the suffix is already sorted (descending), a $O(k)$ reverse is used instead of an $O(k \log k)$ sort.

Time Complexity

$O(n)$

n ➔ Length of the array

O(k) ➔ To find the non increasing array suffix and reversing

Space Complexity

$O(1)$ No extra space is used

Solution

class Solution {
    public void nextPermutation(int[] nums) {
        // Time Compelxity: O(n)
        // Space Complexity: O(1)
        if(nums == null || nums.length < 2) return;

        int i = nums.length - 1;
        // Finding the non-decreasing array from reverse (right to left)
        // (Or) finding the non increasing suffix
        while(i > 0 && nums[i-1] >= nums[i]) {
            i--;
        }

        // If the whole array is non increasing suffix
        // Already at the greatest permutation
        // Reverse the array so that in a circular fashion, we get the next lexicographically greatest
        if(i==0) {
            reverse(nums, i);
            return;
        }

        int j = nums.length - 1;
        int pivot = i - 1; // Pivot element is index before non-increasing suffix

        // Finding the min-max of the pivot element in non increasing suffix
        while(nums[pivot] >= nums[j]) {
            j--;
        }

        // Swap the pivot and min max to make it just next lexicographically greater permutation
        swap(nums, pivot, j);
        // Reverse the non-increasing suffix which makes it non-decreasing
        // Since the pivot is swapped and reversing the suffix makes sure it is the next greater permutation
        reverse(nums, i);
        return;
    }

    private static void swap(int[] nums, int i, int j) {
        int temp = nums[i];
        nums[i] = nums[j];
        nums[j] = temp;
    }

    private static void reverse(int[] nums, int start) {
        int end = nums.length - 1;

        while(start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}

class Solution {
    public void nextPermutation(int[] nums) {
        // n -> Number of elements in nums
        // Time Complexity: O(n)
        // Traversing through the nums array three times so 3 * O(n) = O(n)

        // Space Complexity: O(1), auxillary space, no extra space is used

        // Find the pivot index, which is the index of the first element that can be modified to obtain a greater permutation
        int pivotIndex = findPivotIndex(nums);
        
        // If no pivot index is found, it means the given sequence is in descending order
        // Reverse the entire sequence to obtain the first permutation
        if (pivotIndex == -1) {
            reverse(nums, pivotIndex + 1);
            return;
        }
        
        // Find the index of the last element greater than the pivot value
        int lastPivotIndex = lastPivotIndexWhichIsGreaterThanThreshold(nums, nums[pivotIndex]);
        
        // Swap the pivot element with the last pivot index
        swap(nums, pivotIndex, lastPivotIndex);
        
        // Reverse the subarray after the pivot index to ensure it is in ascending order
        reverse(nums, pivotIndex + 1);
    }

    // Find the pivot index, which is the index of the first element that can be modified to obtain a greater permutation
    private int findPivotIndex(int[] nums) {
        // Start the iteration from the second-to-last element (index nums.length - 2) going backwards
        // We start from the second-to-last element because we want to find the first element that is smaller than its next element
        // If we start from the last element (index nums.length - 1), it won't be possible to find a smaller element
        for (int i = nums.length - 2; i >= 0; i--) {
            // If the current element is smaller than its next element, it can be modified to obtain a greater permutation
            // Return the current index as the pivot index
            if (nums[i] < nums[i + 1]) {
                return i;
            }
        }
    
        // If no pivot index is found, it means the given sequence is in descending order
        // Return -1 to indicate that there is no pivot index
        return -1;
    }


    // Find the index of the last element greater than the threshold value
    private int lastPivotIndexWhichIsGreaterThanThreshold(int[] nums, int threshold) {
        int i = nums.length - 1;
        for (; i >= 0; i--) {
            if (nums[i] > threshold) {
                break;
            }
        }
        return i;
    }

    // Swap two elements in the array
    private void swap(int[] nums, int a, int b) {
        int temp = nums[a];
        nums[a] = nums[b];
        nums[b] = temp;
    }

    // Reverse the subarray starting from the given start index
    private void reverse(int[] nums, int start) {
        int end = nums.length - 1;

        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}