0031.Next Permutation

Link: 31. Next Permutation - Medium
Track: NeetCode150

Question

Restate the problem

---

Method 1
Method 2

Method

Approach

• Find pivot (drop point)
  Scan from right to left to find the first index p such that nums[p] < nums[p+1].

  • Everything to the right of p is a non-increasing suffix (already the largest arrangement for that prefix).

• If no pivot exists
  The array is entirely non-increasing (e.g. [3,2,1]), meaning it’s the largest permutation.

  • Reverse the whole array to get the smallest permutation and return.

• Find the “slightly bigger” element
  Scan from right to left to find the first index j such that nums[j] > nums[p].

  • This picks the smallest element greater than pivot (minimal increase).

• Swap pivot and that element
  Swap nums[p] and nums[j].

• Reverse the suffix
  Reverse nums[p+1:] to make the suffix the smallest possible (ascending), ensuring the result is the next permutation.

Complexity

• Time: O(n) (a few right-to-left scans + one reverse)
• Space: O(1) extra (if you reverse in-place with two pointers)

Edge Case

Code

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        '''
                -> swap     -> reverse
        [73621] -> [72 631] -> [72 136]
            ^
        '''
        n = len(nums)
        drop_point = -1
        
        for i in range(n - 1, 0, -1): # 2, 1
            if nums[i-1] < nums[i]:
                drop_point = i - 1
                break
        
        if drop_point == -1:
            nums.reverse()
            return
 
        idx = drop_point + 1
        for idx in range(n - 1, drop_point, -1):
            if nums[idx] > nums[drop_point]:
                nums[idx], nums[drop_point] = nums[drop_point], nums[idx]
                break
            idx += 1
        
        nums[drop_point + 1:] = reversed(nums[drop_point + 1:])

---

History

Jan-23-2026 Peeked

• do not know the solution
• array.reverse() is in place, revered(arr) need assign to a variable