Next Permutation medium

Problem Statement

Given an array of integers nums, find the next lexicographically greater permutation of its elements. If no next greater permutation is possible, find the lexicographically smallest permutation of its elements.

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 first decreasing digit from the right: Iterate from the right end of the array. Find the first index i such that nums[i] < nums[i+1]. If no such index is found, the array is already in descending order (the largest permutation), so we need to reverse the entire array to get the smallest permutation.

2. Find the smallest digit greater than nums[i] to the right: Find the smallest digit in the subarray to the right of i that is greater than nums[i]. Let's call the index of this digit j.

3. Swap nums[i] and nums[j]: Swap the digits at indices i and j.

4. Reverse the subarray to the right of i: Reverse the subarray from index i+1 to the end of the array. This ensures that the remaining digits are in ascending order, creating the lexicographically next permutation.

Explanation

Let's illustrate with nums = [1, 3, 2].

1. Step 1: We iterate from right to left. nums[1] = 3 and nums[2] = 2. Since 3 > 2, i becomes 1.

2. Step 2: We look for the smallest digit greater than nums[1] = 3 in the subarray to the right of i=1. This subarray is [2]. There is no digit greater than 3 in this subarray. In cases like this where the rightmost digit is smaller than all the digits to its left, step 2 is omitted, and step 4 becomes reversing the entire array.

3. Step 3 (This step is omitted for this example): There is no swap.

4. Step 4: We reverse the subarray from index i+1 = 2 to the end. This reverses [2], which remains [2]. Because no element to the right of i was larger than the element at i, we instead must reverse the entire array in this case.

5. Result: If we reverse the entire array [1,3,2], we get [2,3,1].

Now let's try with nums = [1, 5, 8, 4, 7, 6, 5, 3, 1]

1. Step 1: i becomes 5 (because nums[5] = 6 and nums[6] = 5)

2. Step 2: The smallest digit greater than nums[5] = 6 in the subarray [5, 3, 1] is 6. There isn't a value greater than 6, so the smallest value larger than 6, which is 7 should be used instead.

3. Step 3: Swap nums[5] and nums[4]. The array becomes [1, 5, 8, 4, 6, 7, 5, 3, 1]

4. Step 4: Reverse the subarray to the right of index 5: [7, 5, 3, 1] becomes [1, 3, 5, 7].

5. Result: The final array is [1, 5, 8, 4, 6, 1, 3, 5, 7]

Code

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        """
        Do not return anything, modify nums in-place instead.
        """
        n = len(nums)
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:
            i -= 1

        if i >= 0:
            j = n - 1
            while j > i and nums[j] <= nums[i]:
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]

        left = i + 1
        right = n - 1
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

Complexity

• Time Complexity: O(n), where n is the length of the input array. We iterate through the array at most twice.
• Space Complexity: O(1). The algorithm operates in-place, using only a constant amount of extra space.