Next Permutation - Leetcode Solution

Problem:

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such an arrangement is not possible, it must rearrange it as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place, 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]

Example 3:

Input: nums = [1,1,5] Output: [1,5,1]

Example 4:

Input: nums = [1] Output: [1]

Solution:

The first step to solving the problem is to understand what is meant by lexicographically greater permutation.

A permutation is lexicographically greater if it appears after the given permutation when the permutations are arranged in the increasing order. For example, [3,2,1] is not lexicographically greater than [1,2,3] because it appears before it in the increasing order of permutations.

One way to find the next lexicographically greater permutation is to iterate through the array from right to left and find the first pair of adjacent elements where the left element is smaller than the right element. For example, in the array [1,2,5,4,3], the pair is (2,5) because 2 is smaller than 5.

Once we have found this pair of elements, we need to find the smallest element in the array that is greater than the left element of the pair. In the example above, the smallest element greater than 2 is 3.

Then, we swap the left element with this smallest element. After the swap, the array becomes [1,3,5,4,2].

Finally, we reverse the subarray starting from the right element of the pair (inclusive) to the end of the array. In the example above, the subarray is [5,4,2], and the reversed subarray becomes [2,4,5]. The final result is [1,3,2,4,5].

If we cannot find such a pair of adjacent elements, it means that the array is already in the lexicographically highest order, so we just reverse the entire array to get the lowest possible order.

Here's the implementation of the above approach in Python:

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

    # Find the first pair of adjacent elements where the left element is smaller than the right element
    while i >= 0 and nums[i] >= nums[i+1]:
        i -= 1
    
    if i >= 0:
        # Find the smallest element in the array that is greater than nums[i]
        j = n - 1
        while j >= 0 and nums[j] <= nums[i]:
            j -= 1
        
        # Swap nums[i] and nums[j]
        nums[i], nums[j] = nums[j], nums[i]
    
    # Reverse the subarray starting from the right element of the pair
    # to the end of the array
    left, right = i+1, n-1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

Time Complexity

The time complexity of the above approach is O(n), where n is the length of the input array.

Space Complexity

The space complexity of the above approach is O(1), as we are modifying the input array in place and not using any extra space.

1