Next Permutation medium

Problem Statement

Implement nextPermutation, which rearranges the given nums array into the lexicographically next greater permutation of its elements. If no next greater permutation is possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in place and use only constant extra memory.

Example 1

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

Example 2

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

Steps and Explanation

The algorithm involves finding the first digit from the right that is smaller than the digit to its right. This is the pivot. Then we find the smallest digit to the right of the pivot that is larger than the pivot. We swap these two digits. Finally, we reverse the subarray to the right of the pivot to get the lexicographically next permutation.

Let's trace Example 1 ([1,2,3]):

1. Find Pivot: We scan from right to left. 3 > 2, 2 > 1. No pivot found initially.
2. Find Next Greater: Since no pivot was found, this means the array is in descending order and the next permutation is the ascending order.
3. Reverse: If a pivot is found, we would swap and reverse the right portion. In this case, we just reverse the entire array, resulting in the smallest possible order: [1,2,3] is already the next permutation. If we had [1,3,2], we would swap 2 and 3, and then reverse to get [1,2,3]. If we had [3,1,2], we would swap 1 and 2, and then reverse to get [3,2,1].

Let's trace [3,2,1]:

1. Find Pivot: We scan from right to left. 1 < 2, 2 < 3. No pivot is found.
2. Find Next Greater: No next greater element exists.
3. Reverse: The entire array is reversed to obtain the smallest possible order: [1,2,3].

Let's trace [1,5,1]:

1. Find Pivot: Scanning from right to left: 1 < 5. The pivot is 1.
2. Find Next Greater: The next greater element to the right of 1 is 5.
3. Swap: Swap 1 and 5: [5,1,1]
4. Reverse: Reverse the subarray to the right of the pivot: [5,1,1].

Code (Java)

import java.util.Arrays;

class Solution {
    public void nextPermutation(int[] nums) {
        int n = nums.length;
        int i = n - 2;

        // Find the pivot
        while (i >= 0 && nums[i] >= nums[i + 1]) {
            i--;
        }

        if (i >= 0) {
            int j = n - 1;
            // Find the next greater element
            while (j > i && nums[j] <= nums[i]) {
                j--;
            }
            // Swap
            swap(nums, i, j);
        }

        // Reverse the subarray to the right of the pivot
        reverse(nums, i + 1, n - 1);
    }

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

    private void reverse(int[] nums, int start, int end) {
        while (start < end) {
            swap(nums, start, end);
            start++;
            end--;
        }
    }
}

Complexity

• Time Complexity: O(n) - We iterate through the array at most twice. Reversing a subarray also takes linear time.
• Space Complexity: O(1) - The algorithm operates in place; it doesn't use extra space proportional to the input size.