AlgoMaster Logo

Next Permutation

Last Updated: March 31, 2026

medium

Understanding the Problem

The word "permutation" can make this problem sound more complex than it really is. Here's what we're really doing: given a sequence of numbers, rearrange them into the next sequence that would come after the current one if we listed all possible arrangements in dictionary order.

Think of it like an odometer. The number 1234 is followed by 1235, then 1236, and so on. When the last digit maxes out, you increment the next digit and reset. Permutations work the same way, except instead of digits 0-9, you're working with the elements of the array, and instead of simple addition, you're rearranging positions.

The key observation is this: to get the next permutation, you need to find the rightmost position where the sequence can still "grow," make the smallest possible increase at that position, and then arrange everything after it in the smallest possible order.

Key Constraints:

  • 1 <= nums.length <= 100 → With n up to 100, even O(n^2) means just 10,000 operations. So efficiency is not the main challenge here. The real difficulty is getting the algorithm right.
  • 0 <= nums[i] <= 100 → Values are non-negative integers. Duplicates are possible (since values can repeat), which means we need to handle cases like [1, 1, 5] correctly.
  • in place, constant extra memory → We cannot create a copy of the array or use extra data structures. This rules out generating all permutations and searching for the next one.

Approach 1: Generate All Permutations (Brute Force)

Intuition

The most straightforward approach: generate every possible permutation of the array, sort them all in lexicographic order, find the current permutation in the list, and return the next one. If the current permutation is the last one, wrap around to the first.

This makes the problem trivially correct, but it's wildly impractical. For an array of length n, there are n! permutations. Even with n = 10, that's 3.6 million permutations to generate and sort. With n = 20, it's over 2 quintillion. And the problem says we need constant extra memory, which this approach violates spectacularly.

Still, thinking about this approach helps us understand the problem. When we list permutations in order, what pattern do the transitions follow?

Algorithm

  1. Generate all permutations of the input array.
  2. Sort the permutations in lexicographic order.
  3. Find the current array in the sorted list.
  4. Return the next permutation in the list (wrapping around to the first if needed).

Example Walkthrough

Input:

0
1
1
2
2
3
nums

All permutations sorted: [1,2,3] [1,3,2] [2,1,3] [2,3,1] [3,1,2] [3,2,1]. Current is [1,2,3] at position 0. Next is position 1:

0
1
1
3
2
2
nums

Code

This approach is conceptually simple but completely impractical for larger inputs. Can we compute the next permutation directly from the current one without generating all permutations?

Approach 2: Optimal (Single Pass with Suffix Reversal)

Intuition

Let's study what happens when we list permutations of [1, 2, 3, 4] in order. The rightmost elements change most frequently, just like the least-significant digits of a number. And when the suffix is already in descending order (it can't get any bigger), we "carry over" to the next position.

Here's the algorithm distilled: scan from the right to find the first position where the sequence can still grow (the "pivot"), swap the pivot with the smallest larger element in the suffix, and reverse the suffix to make it the smallest possible arrangement.

Algorithm

  1. Start from the right end of the array. Find the first index i such that nums[i] < nums[i + 1]. This is the pivot.
  2. If no pivot exists (the array is in descending order), reverse the entire array and return.
  3. From the right end, find the first index j such that nums[j] > nums[i].
  4. Swap nums[i] and nums[j].
  5. Reverse the subarray from i + 1 to the end.

Example Walkthrough

1Initialize: scan right to left to find pivot
0
1
1
3
2
5
3
4
i
4
2
1/7

Code