Looking for good programming challenges?

Use the search below to find our solutions for selected questions!

Next permutation challenge

Sharing is caring!

Problem statement
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).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

Sample input 1


Sample output 1


Sample input 2


Sample output 2


We will iterate over the array backwards, starting from the end and search for the first element that we can swap with a preceding element. The condition is, that the preceding element must be smaller than the current element. In other words, we want to increase the number that resides at the index, maxIndex of the preceding element by swapping. For instance, if the input were to be \left[4, 2, 0, 2, 3, 2, 0\right] we would start with the trailing 0 and try to find a preceding element that is smaller. For 0 we don’t have such an element. We then continue with 2 at index 5 and find that we can swap it with the 0 at index 2. We note down both indices (indices maxIndex = 2 and cursorIndex = 5) and continue. Next, we search a preceding element for the element at index 4. We find that 3 is greater than the element at index 3 and compare those indices with maxIndex and cursorIndex. We can see that from the previous iteration we noted down index 2 and now we have found a larger index, 3. For our purpose 3 is better than 2 because it still results in a larger permutation when we swap, but still smaller than when we would swap index 2. That is why we update our maxIndex and cursorIndex to maxIndex = 3 and cursorIndex = 4. We continue our backwards iteration until we surpass maxIndex.

Finally, we just have to sort the part of the array starting at index maxIndex + 1 in ascending order.

Full code

class Solution(object):
    def nextPermutation(self, nums):
        :type nums: List[int]
        :rtype: void Do not return anything, modify nums in-place instead.
        print(nums, end='', flush=True)
        r = len(nums) - 1
        i = -1
        max_index = -1
        cursor_index = -1
        while True and r >= max_index:
            cursor = r
            i = cursor - 1
            while i >= 0 and nums[cursor] <= nums[i]:
                i -= 1

            if i >= 0:
                if i > max_index:
                    max_index = i
                    cursor_index = cursor

            r -= 1

        if cursor_index >= 0:
            tmp = nums[cursor_index]
            nums[cursor_index] = nums[max_index]
            nums[max_index] = tmp
            result = nums[:max_index+1] + sorted(nums[max_index+1:])

            for i in range(0, len(result)):
                nums[i] = result[i]

def main():
    solution = Solution()
    solution.nextPermutation([1, 2, 3])
    solution.nextPermutation([1, 2, 0])
    solution.nextPermutation([2, 4, 1, 3, 2])
    solution.nextPermutation([1, 1, 5])
    solution.nextPermutation([3, 2, 1])
    solution.nextPermutation([1, 3, 2])

if __name__ == "__main__": main()