31. Next Permutation

#permutation #array #two-pointers

Problem

Next Permutation - LeetCodeLeetCode

Intuition

Time Complexity

Space Complexity

Solution

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--;
        }
    }
}