LeetCode 31 - Next Permutation

The problem asks us to modify an integer array so that it becomes the next lexicographically greater permutation of its current arrangement. A permutation is simply an ordering of the elements. Lexicographical order works the same way dictionary order works for words.

leetcodemediumarraytwo-pointers

LeetCode Problem 31

Difficulty: 🟡 Medium
Topics: Array, Two Pointers

Solution

Problem Understanding

The problem asks us to modify an integer array so that it becomes the next lexicographically greater permutation of its current arrangement.

A permutation is simply an ordering of the elements. Lexicographical order works the same way dictionary order works for words. When comparing two arrays, we compare elements from left to right until we find the first difference. The array with the larger number at that position is considered larger.

For example:

  • [1,2,3] < [1,3,2]
  • [1,3,2] < [2,1,3]

The task is to transform the given array into the very next arrangement in this ordering sequence.

If the current arrangement is already the largest possible permutation, such as [3,2,1], then there is no larger permutation available. In that case, we must wrap around to the smallest possible permutation, which is the ascending order arrangement.

A very important constraint is that the modification must happen in place. We are not allowed to allocate another array proportional to the input size. Only constant extra memory may be used.

The input size is relatively small, at most 100 elements, but the number of permutations grows factorially. Even for modest array sizes, generating all permutations becomes computationally infeasible. This means we need a direct mathematical or structural observation instead of brute force generation.

Several edge cases are important:

  • Arrays already in descending order, such as [5,4,3,2,1]
  • Arrays with duplicate values, such as [1,1,5]
  • Arrays of length 1
  • Arrays where only the final two elements need swapping
  • Arrays where a large suffix must be rearranged

The problem guarantees that all values are integers and the array length is at least 1.

Approaches

Brute Force Approach

A brute force solution would generate every possible permutation of the array, sort them lexicographically, locate the current permutation, and then select the next one.

This works because lexicographical ordering fully defines the permutation sequence. Once all permutations are generated and sorted, finding the next permutation becomes straightforward.

However, this approach is extremely inefficient. An array of length n has n! permutations. Even for n = 10, this already exceeds 3 million permutations. The memory and runtime costs become enormous very quickly.

Additionally, the problem explicitly requires constant extra memory and in-place modification, which the brute force solution violates.

Optimal Approach

The key insight is that we do not need to generate all permutations.

Instead, we can directly construct the next lexicographically larger arrangement by observing how permutations evolve.

Consider the array from right to left. If a suffix is strictly decreasing, then that suffix is already the largest possible arrangement for those elements. To create a larger permutation, we must modify something before that suffix.

The algorithm works by:

  1. Finding the first position from the right where the sequence stops decreasing
  2. Swapping that value with the next larger value to its right
  3. Reversing the suffix to make it as small as possible

This produces the smallest permutation that is still larger than the original arrangement.

Approach Time Complexity Space Complexity Notes
Brute Force O(n! × n) O(n! × n) Generates and sorts all permutations
Optimal O(n) O(1) Finds the next permutation directly in-place

Algorithm Walkthrough

Step-by-Step Algorithm

  1. Traverse the array from right to left to find the pivot index.

We look for the first index i such that:

nums[i] < nums[i + 1]

This identifies the first position where the array can still be increased.

Everything to the right of this position forms a decreasing suffix, meaning it is already the largest possible arrangement of those elements. 2. If no pivot exists, reverse the entire array.

If the array is completely decreasing, such as [3,2,1], then it is already the largest permutation.

The next permutation in lexicographical order must therefore wrap around to the smallest permutation.

Reversing the entire array produces ascending order. 3. Find the rightmost successor to the pivot.

Starting from the end of the array, locate the first element greater than nums[pivot].

Because the suffix is decreasing, the first larger element encountered from the right is the smallest valid replacement. 4. Swap the pivot and successor.

This increases the permutation while changing the array as little as possible. 5. Reverse the suffix after the pivot.

The suffix is currently in decreasing order. After the swap, we want the smallest possible suffix arrangement to ensure we get the immediate next permutation instead of skipping ahead.

Reversing converts it into ascending order.

Why it works

The decreasing suffix represents the largest possible arrangement of those elements. The pivot is the first place where we can still make the permutation larger.

Swapping the pivot with the smallest larger element ensures the increase is minimal. Reversing the suffix afterward guarantees the remaining elements are arranged in the smallest possible order.

Together, these operations produce the smallest lexicographically larger permutation, which is exactly the next permutation.

Python Solution

from typing import List

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

        n = len(nums)

        # Step 1: Find the pivot
        pivot = n - 2

        while pivot >= 0 and nums[pivot] >= nums[pivot + 1]:
            pivot -= 1

        # Step 2: If pivot exists, find successor and swap
        if pivot >= 0:
            successor = n - 1

            while nums[successor] <= nums[pivot]:
                successor -= 1

            nums[pivot], nums[successor] = nums[successor], nums[pivot]

        # Step 3: Reverse the suffix
        left = pivot + 1
        right = n - 1

        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

The implementation begins by searching for the pivot index from right to left. The pivot is the first position where the sequence increases when viewed from right to left.

If no pivot is found, the array is entirely decreasing, meaning it is already the largest permutation. In that case, reversing the whole array transforms it into the smallest permutation.

If a pivot exists, the code finds the rightmost element greater than the pivot value. Since the suffix is decreasing, this guarantees the smallest valid increase.

After swapping, the suffix is reversed in-place using two pointers. This converts the decreasing suffix into ascending order, ensuring the resulting permutation is the immediate next lexicographical arrangement.

The algorithm uses only constant extra memory because all operations happen directly within the original array.

Go Solution

func nextPermutation(nums []int) {
	n := len(nums)

	// Step 1: Find pivot
	pivot := n - 2

	for pivot >= 0 && nums[pivot] >= nums[pivot+1] {
		pivot--
	}

	// Step 2: Find successor and swap
	if pivot >= 0 {
		successor := n - 1

		for nums[successor] <= nums[pivot] {
			successor--
		}

		nums[pivot], nums[successor] = nums[successor], nums[pivot]
	}

	// Step 3: Reverse suffix
	left := pivot + 1
	right := n - 1

	for left < right {
		nums[left], nums[right] = nums[right], nums[left]
		left++
		right--
	}
}

The Go implementation follows the same logic as the Python version.

Go slices are mutable references to underlying arrays, so modifications occur in-place automatically. No additional array allocation is necessary.

Unlike Python, Go does not have built-in reverse operations for slices, so the suffix reversal is implemented manually with two pointers.

Integer overflow is not a concern because the algorithm only compares and swaps existing values.

Worked Examples

Example 1

Input:

[1,2,3]

Step 1: Find Pivot

Index Value Comparison
1 2 2 < 3, pivot found

Pivot index = 1

Step 2: Find Successor

Starting from the right:

Index Value Condition
2 3 3 > 2

Successor index = 2

Step 3: Swap

[1,3,2]

Step 4: Reverse Suffix

Suffix after pivot is [2], already sorted.

Final result:

[1,3,2]

Example 2

Input:

[3,2,1]

Step 1: Find Pivot

Index Comparison
1 2 >= 1
0 3 >= 2

No pivot found.

Step 2: Reverse Entire Array

[1,2,3]

Final result:

[1,2,3]

Example 3

Input:

[1,1,5]

Step 1: Find Pivot

Index Value Comparison
1 1 1 < 5

Pivot index = 1

Step 2: Find Successor

Index Value Condition
2 5 5 > 1

Successor index = 2

Step 3: Swap

[1,5,1]

Step 4: Reverse Suffix

Suffix contains one element.

Final result:

[1,5,1]

Complexity Analysis

Measure Complexity Explanation
Time O(n) Each traversal scans the array at most once
Space O(1) Only a few variables are used

The algorithm performs three linear operations:

  • Finding the pivot
  • Finding the successor
  • Reversing the suffix

Each operation takes at most O(n) time, and they occur sequentially rather than nested. Therefore the overall runtime remains linear.

All modifications happen directly inside the input array, so only constant extra space is used.

Test Cases

from typing import List

class Solution:
    def nextPermutation(self, nums: List[int]) -> None:
        n = len(nums)

        pivot = n - 2

        while pivot >= 0 and nums[pivot] >= nums[pivot + 1]:
            pivot -= 1

        if pivot >= 0:
            successor = n - 1

            while nums[successor] <= nums[pivot]:
                successor -= 1

            nums[pivot], nums[successor] = nums[successor], nums[pivot]

        left = pivot + 1
        right = n - 1

        while left < right:
            nums[left], nums[right] = nums[right], nums[left]
            left += 1
            right -= 1

sol = Solution()

nums = [1, 2, 3]
sol.nextPermutation(nums)
assert nums == [1, 3, 2]  # basic increasing case

nums = [3, 2, 1]
sol.nextPermutation(nums)
assert nums == [1, 2, 3]  # completely decreasing array

nums = [1, 1, 5]
sol.nextPermutation(nums)
assert nums == [1, 5, 1]  # duplicate values

nums = [1]
sol.nextPermutation(nums)
assert nums == [1]  # single element

nums = [1, 3, 2]
sol.nextPermutation(nums)
assert nums == [2, 1, 3]  # pivot in middle

nums = [2, 3, 1]
sol.nextPermutation(nums)
assert nums == [3, 1, 2]  # suffix reversal needed

nums = [1, 5, 1]
sol.nextPermutation(nums)
assert nums == [5, 1, 1]  # duplicates after pivot

nums = [2, 2, 0, 1]
sol.nextPermutation(nums)
assert nums == [2, 2, 1, 0]  # repeated elements with suffix swap

nums = [5, 4, 7, 5, 3, 2]
sol.nextPermutation(nums)
assert nums == [5, 5, 2, 3, 4, 7]  # large suffix reversal

nums = [1, 2]
sol.nextPermutation(nums)
assert nums == [2, 1]  # smallest non-trivial case
Test Why
[1,2,3] Basic next permutation
[3,2,1] Largest permutation wraps around
[1,1,5] Handles duplicates correctly
[1] Single-element boundary case
[1,3,2] Pivot not at array start
[2,3,1] Requires suffix reversal
[1,5,1] Duplicate handling after swap
[2,2,0,1] Mixed duplicates and decreasing suffix
[5,4,7,5,3,2] Complex suffix rearrangement
[1,2] Smallest non-trivial array

Edge Cases

Completely Decreasing Array

An input like [5,4,3,2,1] is already the largest possible permutation. A naive implementation might fail because there is no pivot index where nums[i] < nums[i+1].

The algorithm handles this by detecting that no pivot exists and reversing the entire array. This correctly produces the smallest permutation, [1,2,3,4,5].

Arrays with Duplicate Values

Duplicate values can create subtle bugs if the wrong successor element is selected.

For example:

[1,5,1]

The algorithm specifically searches from the right side for the first value greater than the pivot. This guarantees the smallest valid increase and preserves lexicographical correctness even with duplicates.

Single Element Arrays

An array containing only one element already represents both the smallest and largest permutation.

Some implementations accidentally access invalid indices when searching for the pivot. This solution safely initializes the pivot index and naturally skips unnecessary operations when the array length is 1.

Large Decreasing Suffix

Inputs like:

[1,4,3,2]

contain a long decreasing suffix.

A common mistake is sorting the suffix instead of reversing it. Since the suffix is guaranteed to already be in decreasing order, reversing is sufficient and more efficient.

The implementation correctly uses a two-pointer reversal, maintaining O(n) runtime and constant extra space.