Skip to main content

Next Permutation

LeetCode 31 | Difficulty: Medium​

Problem Description​

A permutation of an array of integers is an arrangement of its members into a sequence or linear order.

The next permutation of an array of integers is the next lexicographically greater permutation of its integer. If such arrangement is not possible, the array must be rearranged as the lowest possible order (i.e., sorted in ascending order).

The replacement must be in place and use only constant extra memory.

Constraints​

  • 1 <= nums.length <= 100
  • 0 <= nums[i] <= 100

Examples​

Example 1:

Input: nums = [1,2,3]
Output: [1,3,2]

Example 2:

Input: nums = [3,2,1]
Output: [1,2,3]
Explanation: No next permutation exists, so we return the lowest order.

Example 3:

Input: nums = [1,1,5]
Output: [1,5,1]

Approach​

The algorithm works in 4 steps:

Step 1: Find the pivot

  • Scan from right to left, find the first element that is smaller than its right neighbor
  • This is the "pivot" position where we can increase the permutation

Step 2: Find the successor

  • Scan from right to left, find the smallest element larger than the pivot

Step 3: Swap

  • Swap the pivot with its successor

Step 4: Reverse

  • Reverse everything to the right of the original pivot position

Visual Walkthrough​

Example: [1, 2, 3, 8, 5, 1] → [1, 2, 5, 1, 3, 8]

Step 1: Find pivot (first decreasing element from right)
[1, 2, 3, 8, 5, 1]
       ↑
    pivot=3 (index 2)

Step 2: Find successor (smallest element > pivot, from right)
[1, 2, 3, 8, 5, 1]
             ↑
        successor=5 (index 4)

Step 3: Swap pivot and successor
[1, 2, 5, 8, 3, 1]

Step 4: Reverse elements after pivot's original position
[1, 2, 5, 1, 3, 8]
         └──────┘ reversed

Complexity Analysis​

  • Time Complexity: $O(N)$ — At most two scans through the array + one reversal
  • Space Complexity: $O(1)$ — In-place modification

Solution​

public void NextPermutation(int[] nums)
{
    if (nums.Length <= 1) return;

    // Step 1: Find the pivot (rightmost element smaller than its successor)
    int pivot = -1;
    for (int i = nums.Length - 1; i >= 1; i--)
    {
        if (nums[i - 1] < nums[i])
        {
            pivot = i - 1;
            break;
        }
    }
    
    // If no pivot found, array is in descending order - reverse entire array
    if (pivot == -1)
    {
        Array.Reverse(nums);
        return;
    }
    
    // Step 2: Find the successor (smallest element greater than pivot, from right)
    int successor = -1;
    for (int i = nums.Length - 1; i > pivot; i--)
    {
        if (nums[i] > nums[pivot])
        {
            successor = i;
            break;
        }
    }
    
    // Step 3: Swap pivot and successor
    Swap(nums, pivot, successor);
    
    // Step 4: Reverse the suffix after pivot
    Array.Reverse(nums, pivot + 1, nums.Length - pivot - 1);
}

void Swap(int[] nums, int i, int j)
{
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}

Interview Tips​

  • Why reverse works: The suffix after pivot is in descending order. Reversing makes it ascending (smallest possible arrangement)
  • Edge cases:
    • Already largest permutation [3,2,1] → return smallest [1,2,3]
    • All same elements [1,1,1] → no change
    • Two elements [1,2] → swap to [2,1]
  • Follow-up: Implement Previous Permutation (same logic, but find first increasing pair from right)
  • Common mistakes:
    • Forgetting to handle no-pivot case
    • Off-by-one errors in the reverse range