Next Permutation

Problem

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers. If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

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

Examples:

1,2,3 → 1,3,2  
3,2,1 → 1,2,3  
1,1,5 → 1,5,1  

Input

• nums - Array of integers

Approach

This is a tricky problem. The brute force solution is to generate all permutations of nums and sort all of them, and retrieve the array that is sorted right after nums. This can easily be about \(n!\) time and space complexity, so this is not the ideal solution.

The intuition here is to study the examples carefully.

In particular, \([5, 4, 3, 2, 1]\) is the best example to look at. The next permutation of this array does not exist, simply because this is the highest permutation there is. The characteristic of this array is that all numbers are in descending order.

Thus, when given an array such as \([5, 4, 0, 2, 1]\), it is logical to start from the right side of the array and keep looking left until we encounter an index \(i\) such that \(nums[i] \geq nums[i+1]\) -- or in other words, when we have found an element that is not in descending order.

Once we have found the first element that is not in descending order from the right (call the index, \(swap_i\)), we'll have to search the right side now for an element that is just larger than that element. This entails that we traverse all the way back to the end of the array.

Once we find the element that is just larger than \(nums[swapi]\) we now swap \(nums[swapi] and nums[just_larger]\).

After the swap though, we see that the suffix array (\(nums{swapi + 1}\) and onwards) are still not in the correct placements. Since we have replaced the value at \(swap_i\) with an element that is just larger, all elements to the right should be minimized. To do that, we can simply sort them in ascending order.

A more elegant solution is to make use of the fact that all elements to the right of \(swap_i\) were already in descending order; all we have to do is reverse that sublist to get them into ascending order.

Solution

    def nextPermutation(self, nums: 'List[int]') -> 'None':
        """
        Do not return anything, modify nums in-place instead.
        """
        if not nums:
            return

        swap_i = -1
        for i in reversed(range(0, len(nums) - 1)):
            if nums[i] < nums[i+1]:
                swap_i = i
                break

        if swap_i > -1:
            j = swap_i + 1
            for i in range(swap_i + 1, len(nums)):
                if nums[i] > nums[swap_i] and nums[i] <= nums[j]:
                    j = i

            nums[swap_i], nums[j] = nums[j], nums[swap_i]

        nums[swap_i + 1:] = reversed(nums[swap_i + 1:])