💬 Discord
Sign In
NeetCode #818LC-31MediumGreedy
← Back to All Problems

#818 · #31 · Next Permutation(下一个排列)

📌 Problem Statement & Constraints

A permutation of integers is given as nums. Rearrange it in place into the next permutation in lexicographic order. If no larger permutation exists, rearrange it into the lowest possible order (ascending). The replacement must be in place and use only constant extra memory. Constraints: 1 <= nums.length <= 100, 0 <= nums[i] <= 100.

💡 Core Algorithmic Approaches

  1. Find the rightmost index i with nums[i] < nums[i+1]: everything to its right is non-increasing, so that suffix is already the largest arrangement of those values.
  2. If no such i exists the array is descending, so the next permutation is the ascending order -- reverse the whole array.
  3. Otherwise find the rightmost j > i with nums[j] > nums[i] (the smallest value larger than nums[i] on the descending suffix).
  4. Swap them, then reverse the suffix to make it ascending, which yields the smallest arrangement larger than the current one.

💻 Benchmark Python3 Implementation

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)
        i = n - 2
        while i >= 0 and nums[i] >= nums[i + 1]:   # rightmost ascent
            i -= 1
        if i >= 0:
            j = n - 1
            while nums[j] <= nums[i]:              # smallest larger value on the right
                j -= 1
            nums[i], nums[j] = nums[j], nums[i]
        lo, hi = i + 1, n - 1                      # reverse the descending suffix
        while lo < hi:
            nums[lo], nums[hi] = nums[hi], nums[lo]
            lo += 1
            hi -= 1

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each of the three passes is linear.
💾 Space Complexity
O(1): in-place swaps.

⚠️ Interview Pitfalls & Follow-ups

  • Using nums[i] > nums[i+1] for the pivot: the pivot is the last position where the sequence still rises, i.e. nums[i] < nums[i+1].
  • Picking the leftmost larger element: the rightmost one is the smallest value greater than the pivot, which keeps the suffix maximal after reversal.
  • Reversing instead of sorting the suffix: the suffix is non-increasing, so reversing it makes it non-decreasing in linear time -- sorting would be slower and unnecessary.
  • Forgetting the fully descending case: when i ends at -1 the suffix must be reversed from index 0, which the code does because lo = i + 1 = 0.