Next Permutation medium

Problem Statement

Implement nextPermutation, which takes an integer array nums and finds 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, so do not allocate 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

The algorithm to find the next permutation involves these steps:

  1. Find the pivot: Start from the right end of the array and find the first element (pivot) that is smaller than its right neighbor. If no such element is found, the array is already in descending order (the largest permutation), so we reverse it to get the smallest permutation.

  2. Find the successor: Find the smallest element to the right of the pivot that is greater than the pivot. This element is the successor.

  3. Swap: Swap the pivot and the successor.

  4. Reverse: Reverse the subarray to the right of the pivot. This ensures the remaining elements are in ascending order, creating the next lexicographically greater permutation.

Explanation

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

  1. Find pivot: We start from the right. 3 > 2, 2 > 1. There's no pivot; the array is already sorted in ascending order. This means it's the smallest permutation, and the next permutation is the largest one which will be done by reversing it. This case is handled specially as explained in the code.

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

  1. Find pivot: We start from the right. 1 < 2, 2 < 3. The pivot is 1.

  2. Find successor: There is no element to the right of 1. So the next step of finding the successor is not performed.

  3. Swap: (There's no successor, so no swap).

  4. Reverse: The subarray to the right of the pivot (which is an empty array in this case) is reversed which is a no-op. Then, the entire array needs to be reversed because it was already in descending order. The whole array is reversed resulting in [1,2,3].

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

  1. Find pivot: 2 < 3. The pivot is 2.

  2. Find successor: The successor is 3 (the only element to the right of 2 that's greater than 2).

  3. Swap: Swap 2 and 3: [1,3,2] becomes [1,2,3].

  4. Reverse: Reverse the subarray to the right of the pivot (which is just 3): [1,2,3] remains [1,2,3].

The next permutation is therefore [1,3,2].

Code

function nextPermutation(nums: number[]): void {
    let i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i + 1]) {
        i--;
    }

    if (i >= 0) {
        let j = nums.length - 1;
        while (nums[j] <= nums[i]) {
            j--;
        }
        [nums[i], nums[j]] = [nums[j], nums[i]];
    }
    reverse(nums, i + 1);
};

function reverse(nums: number[], start: number): void {
    let left = start;
    let right = nums.length - 1;
    while (left < right) {
        [nums[left], nums[right]] = [nums[right], nums[left]];
        left++;
        right--;
    }
}

Complexity

  • Time Complexity: O(n), where n is the length of the input array. The algorithm iterates through the array at most twice.
  • Space Complexity: O(1). The algorithm performs the operations in place; no extra space is used beyond a few variables.