Problem Statement in English

You’re given an array of integers nums representing a permutation of numbers.

Your task is to modify nums in-place to the next lexicographically greater permutation of numbers.

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

You must use only constant extra memory.

Approach

This is honestly a BS problem.

Short of an absolute miracle, there’s no way you can just “find” the next permutation without previously having done this, and mugged it up. Whatever.

Here’s the deal (just mug it up, seriously):

  • Find the largest index i such that nums[i] < nums[i + 1]. If no such index exists, the permutation is the last permutation, so we sort the array in ascending order and return.
  • Find the smallest number on the right side of index i which is larger than nums[i]. Let’s call its index nextBiggerIndex.
  • Swap the values at indices i and nextBiggerIndex.
  • Finally, sort the sub-array to the right of index i in ascending order.

See my point? Yea. BS.

Solution in Python


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

        for i in reversed(range(N - 1)):
            if nums[i] < nums[i + 1]:
                break
        else:
            nums.sort()
            return

        nextBigger = max(nums[i + 1 :])
        nextBiggerIndex = -1

        for j in range(i + 1, N):
            if nums[i] < nums[j] <= nextBigger:
                nextBigger = nums[j]
                nextBiggerIndex = j

        nums[i], nums[nextBiggerIndex] = nums[nextBiggerIndex], nums[i]
        nums[i + 1:] = sorted(nums[i + 1:])

Complexity

  • Time: O(Nlog⁡N)O(N \log N)
    Since we may need to sort a sub-array which can take up to O(Nlog⁡N)O(N \log N) time.

  • Space: O(1)O(1)
    Since we are modifying the array in-place and using only constant extra memory.

Mistakes I Made

I obviously had to look this BS up.

And we are done.