Domain 2MediumCORE

Next Permutation

We are given an integer list nums and need to rearrange its elements into the lexicographically next greater permutation in-place. If no such arrangement exists (meaning we have reached the highest possible order, e.g., [3, 2, 1]), we must reset it to the lowest possible order (ascending sort).

Domain: Medium•Updated: 2026-08-31
#Algorithms#LeetCode#qwen3.5:9b#Array

31. Next Permutation

Model: qwen3.5:9b
Topics: Array
FAANG asked: 1
Acceptance rate: 33.9%


Problem Breakdown

We are given an integer list nums and need to rearrange its elements into the lexicographically next greater permutation in-place. If no such arrangement exists (meaning we have reached the highest possible order, e.g., [3, 2, 1]), we must reset it to the lowest possible order (ascending sort).

Key Constraints:

  • In-Place Modification: We cannot return a new list; nums itself must be mutated.
  • Constant Extra Space: O(1)O(1) auxiliary memory is required, ruling out sorting or generating all permutations.
  • Edge Cases to Consider: Single element arrays (no change), strictly decreasing sequences (reset to ascending), and duplicate values within the array.

Intuition

A brute-force approach would be to generate every possible permutation (N!N! complexity) until we find one greater than the current input, or sort all permutations lexicographically. This is computationally infeasible for N>10N > 10. Even generating adjacent swaps and checking if they are larger leads to redundant checks.

The key insight lies in understanding how lexicographical order works: it compares elements from left to right. To find the next permutation, we want to keep the longest possible prefix unchanged because changing an earlier digit increases the value more significantly than a later one. We only need to change the suffix as little as necessary.

Looking at the array from right to left, permutations are ordered based on how “ascending” they end. If a sequence is strictly decreasing (e.g., 5, 4, 3), we cannot make it larger without changing an earlier number. We need to find the first position where this descending trend breaks—specifically, the rightmost index ii such that nums[i] < nums[i+1].

Once found:

  1. The suffix starting at i+1i+1 is in non-increasing order (descending). To get a larger permutation with minimal change, we swap nums[i] with the smallest number in this descending suffix that is strictly greater than it. This ensures the increase is minimized.
  2. After swapping, the suffix remains in descending order but now starts higher. We must reverse the suffix to make it ascending (the lowest possible state for that prefix), ensuring we get the immediate next permutation rather than skipping ahead by a larger jump.

Approach

  1. Find Pivot: Iterate backwards from len(nums) - 2 down to 0. Identify index i where nums[i] < nums[i+1]. If no such element exists (loop finishes without finding), the array is in descending order; reverse the entire list and return.
  2. Find Swap Target: Iterate backwards from len(nums) - 1 down to 0 starting after index i. Find the first element nums[j] strictly greater than nums[i]. This ensures we pick the smallest valid increase for that position.
  3. Swap and Reverse: Swap elements at indices i and j. Finally, reverse the suffix from i+1 to the end of the list (since it is currently descending).

Complexity Analysis

  • Time Complexity: O(N)O(N). We traverse the array a constant number of times: once to find pivot ii, once to find swap index jj, and once to reverse the suffix. All operations are linear scans.
  • Space Complexity: O(1)O(1) auxiliary space (excluding input storage). The reversal is done via pointer manipulation, not creating new lists.

Solution

def nextPermutation(nums):
    n = len(nums)
    
    # Helper function to reverse a subarray in-place
    def reverse(start, end):
        left = start
        right = end - 1
        
        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1
            
    # Step 1: Find the first pivot from right where nums[i] < nums[i+1]
    i = n - 2
    
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
        
    if i == -1:
        # Entire array is non-increasing (descending), reset to ascending order
        reverse(0, n)
        return

    # Step 2: Find the smallest element in suffix greater than pivot nums[i]
    j = n - 1
    while nums[j] <= nums[i]:
        j -= 1
        
    # Swap elements at i and j
    nums[i], nums[j] = nums[j], nums[i]

    # Step 3: Reverse the suffix to make it ascending (smallest possible order)
    reverse(i + 1, n)

Edge Cases Handled

  • Single Element ([1]): The while i >= 0 loop condition fails immediately (ii starts at -1). Code enters the reset block if needed or simply returns since reversing a single element does nothing, maintaining correctness.
  • Strictly Decreasing Sequence ([3,2,1]): Pivot search finds no index where left < right (ii becomes -1). The code reverses the entire array to [1, 2, 3], which is correct (lowest order).
  • Duplicates ([1, 1, 5]): Logic uses strict inequality nums[i] >= nums[i+1]. If duplicates exist in suffix like [5, 4, 4, 3], the search for swap target finds strictly greater values. The pivot logic correctly identifies where order breaks regardless of duplicate values adjacent to each other.
  • Already Ascending ([1,2,3]): Pivot found at index 0. Swap with largest valid element in suffix (index 2). Reverse remaining [3]. Result [1, 3, 2], which is correct next permutation.