Next Permutation

Rearrange an array into the next larger ordering of its values, in place, wrapping to the smallest ordering at the end. A careful scan from the right does it in one pass. Solve it below in Python or JavaScript, then read the walkthrough.

MediumArray Two Pointers Asked at 126 companies incl. Google, Amazon, Meta

Problem

Think of every way to order the values in nums, sorted like words in a dictionary (compare the first position, then the second, and so on). Rearrange nums into the ordering that comes right after the current one.

If nums is already the largest ordering (the values are in non-increasing order), wrap around and rearrange it into the smallest one, which is ascending order.

Modify nums in place using only O(1) extra memory. The function doesn't return anything; the tests check nums after your function finishes.

Example 1

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

Nothing starting with 2 is larger than [2, 4, 3, 1], so the next ordering starts with the next value up, 3, followed by the rest in ascending order.

Example 2

Input: nums = [5, 4, 2]
Output: [2, 4, 5]

This is the largest ordering, so it wraps around to ascending order.

Example 3

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

Duplicates count once per distinct ordering: after [1, 3, 3] comes [3, 1, 3], then [3, 3, 1].

Constraints

1 ≤ nums.length ≤ 10⁴
-100 ≤ nums[i] ≤ 100

Practice

Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.

Get asked Next Permutation in a real interview?

Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.

Start Free Trial

How to solve Next Permutation

Pattern: Rightmost ascent, swap, reverse

To get the smallest possible increase, change the array as far to the right as you can. Read from the right: as long as the values keep rising (... 7, 6, 5, 3, 1 read backwards is 1, 3, 5, 6, 7), that tail is already in its largest arrangement, and no reshuffle of it alone can make the array bigger.

So find the first position from the right, the pivot i, where nums[i] < nums[i + 1]. Everything after it is non-increasing. To grow the array by the least amount, replace nums[i] with the smallest value in the tail that is still bigger than it, then put the tail into its smallest arrangement. Because the tail is non-increasing, that "smallest bigger value" is the rightmost one bigger than nums[i], and after the swap the tail is still non-increasing, so reversing it sorts it ascending.

If there is no pivot, the whole array is the largest ordering, and reversing all of it gives the smallest.

Approach 1: Generate every ordering

Produce all distinct permutations, sort them, find the current one and return the next (or the first). It shows you understand the ordering, but it is factorial in time and memory and is only useful for checking small cases.

Time O(n! · n) · Space O(n! · n)

Approach 2: Find the pivot, then sort the tail

Scan right to left for the pivot, swap it with the smallest larger value in the tail, then sort the tail ascending. Correct, but sorting costs O(n log n) when the tail is already in a known order.

Time O(n log n) · Space O(1)

Approach 3: Pivot, swap, reverse

Set i = n - 2 and move left while nums[i] >= nums[i + 1].
If i >= 0, set j = n - 1 and move left while nums[j] <= nums[i]. Swap nums[i] and nums[j].
Reverse nums[i + 1:] in place with two pointers. When there was no pivot, i is -1 and this reverses the whole array.

The swap keeps the tail non-increasing, which is why a reverse is enough to sort it.

Time O(n) · Space O(1)

Approach	Time	Space
Generate every ordering	O(n! · n)	O(n! · n)
Find the pivot, then sort the tail	O(n log n)	O(1)
Pivot, swap, reverse	O(n)	O(1)

Solution code

Try the practice editor first. Both solutions pass every test above.

Next Permutation solution in Python

def next_permutation(nums: list[int]) -> None:
    n = len(nums)
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

Next Permutation solution in JavaScript

function nextPermutation(nums) {
  const n = nums.length;
  let i = n - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) i--;
  if (i >= 0) {
    let j = n - 1;
    while (nums[j] <= nums[i]) j--;
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }
  for (let left = i + 1, right = n - 1; left < right; left++, right--) {
    [nums[left], nums[right]] = [nums[right], nums[left]];
  }
}

Common mistakes

Using strict comparisons (`>` instead of `>=`) in the scans, which breaks on duplicates like `[1, 3, 3]` or `[4, 4, 4]`.
Swapping the pivot with the largest value in the tail instead of the smallest one that is still bigger.
Sorting or reversing from the pivot itself instead of from the position after it.
Forgetting the wrap-around case and leaving a fully descending array unchanged.
Returning a new array instead of modifying `nums`; the grader only looks at the original list.

What interviewers look for

Interviewers want to hear the reasoning, not a memorized three-step recipe. Explain why the change has to happen as far right as possible, why a non-increasing tail can't be improved on its own, and why the swap leaves the tail sorted descending. Those three points justify every line of the code.

Walk a concrete example with a repeated value, such as [2, 3, 1, 3, 3], before you finish. It catches the > vs >= mistake, which is the most common bug here.

Follow-up questions

How would you find the previous permutation instead?

Mirror every comparison: find the rightmost i with nums[i] > nums[i + 1], swap it with the rightmost tail value smaller than it, then reverse the tail. Without a pivot, reverse the whole array to get the largest ordering.

How do you find the k-th permutation of 1..n directly?

Use the factorial number system. With n values left, each choice of first value covers (n - 1)! orderings, so the index of the first value is (k - 1) / (n - 1)!; remove it and repeat with the remainder. That runs in O(n²) with a list, or O(n log n) with a Fenwick tree.

How would you list every distinct permutation in order?

Sort the array, output it, and call next permutation until it wraps back to ascending order. Duplicates are handled for free because the >= comparisons never produce the same ordering twice.

Companies that ask Next Permutation

Next Permutation is tagged by 126 companies in our interview dataset. The score shows how often it comes up at each company.

and 102 more.

Get live help in the real interview

Working solutions in real time during your actual interview. Invisible to screensharing.

Start Free Trial

No credit card required

Next Permutation

MediumArray Two Pointers Asked at 126 companies incl. Google, Amazon, Meta

Problem

If nums is already the largest ordering (the values are in non-increasing order), wrap around and rearrange it into the smallest one, which is ascending order.

Modify nums in place using only O(1) extra memory. The function doesn't return anything; the tests check nums after your function finishes.

Example 1

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

Nothing starting with 2 is larger than [2, 4, 3, 1], so the next ordering starts with the next value up, 3, followed by the rest in ascending order.

Example 2

Input: nums = [5, 4, 2]
Output: [2, 4, 5]

This is the largest ordering, so it wraps around to ascending order.

Example 3

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

Duplicates count once per distinct ordering: after [1, 3, 3] comes [3, 1, 3], then [3, 3, 1].

Constraints

1 ≤ nums.length ≤ 10⁴
-100 ≤ nums[i] ≤ 100

Practice

Runs 12 tests in your browser. Python loads on the first run (about 6 MB, then cached). Press ⌘/Ctrl + Enter to run.

Get asked Next Permutation in a real interview?

Interview Solver gives you a working solution live, during your actual coding interview. Invisible to screensharing.

Start Free Trial

How to solve Next Permutation

Pattern: Rightmost ascent, swap, reverse

If there is no pivot, the whole array is the largest ordering, and reversing all of it gives the smallest.

Approach 1: Generate every ordering

Time O(n! · n) · Space O(n! · n)

Approach 2: Find the pivot, then sort the tail

Scan right to left for the pivot, swap it with the smallest larger value in the tail, then sort the tail ascending. Correct, but sorting costs O(n log n) when the tail is already in a known order.

Time O(n log n) · Space O(1)

Approach 3: Pivot, swap, reverse

Set i = n - 2 and move left while nums[i] >= nums[i + 1].
If i >= 0, set j = n - 1 and move left while nums[j] <= nums[i]. Swap nums[i] and nums[j].
Reverse nums[i + 1:] in place with two pointers. When there was no pivot, i is -1 and this reverses the whole array.

The swap keeps the tail non-increasing, which is why a reverse is enough to sort it.

Time O(n) · Space O(1)

Approach	Time	Space
Generate every ordering	O(n! · n)	O(n! · n)
Find the pivot, then sort the tail	O(n log n)	O(1)
Pivot, swap, reverse	O(n)	O(1)

Solution code

Try the practice editor first. Both solutions pass every test above.

Next Permutation solution in Python

def next_permutation(nums: list[int]) -> None:
    n = len(nums)
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    left, right = i + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

Next Permutation solution in JavaScript

function nextPermutation(nums) {
  const n = nums.length;
  let i = n - 2;
  while (i >= 0 && nums[i] >= nums[i + 1]) i--;
  if (i >= 0) {
    let j = n - 1;
    while (nums[j] <= nums[i]) j--;
    [nums[i], nums[j]] = [nums[j], nums[i]];
  }
  for (let left = i + 1, right = n - 1; left < right; left++, right--) {
    [nums[left], nums[right]] = [nums[right], nums[left]];
  }
}

Common mistakes

Using strict comparisons (`>` instead of `>=`) in the scans, which breaks on duplicates like `[1, 3, 3]` or `[4, 4, 4]`.
Swapping the pivot with the largest value in the tail instead of the smallest one that is still bigger.
Sorting or reversing from the pivot itself instead of from the position after it.
Forgetting the wrap-around case and leaving a fully descending array unchanged.
Returning a new array instead of modifying `nums`; the grader only looks at the original list.

What interviewers look for

Walk a concrete example with a repeated value, such as [2, 3, 1, 3, 3], before you finish. It catches the > vs >= mistake, which is the most common bug here.

Follow-up questions

How would you find the previous permutation instead?

How do you find the k-th permutation of 1..n directly?

How would you list every distinct permutation in order?

Sort the array, output it, and call next permutation until it wraps back to ascending order. Duplicates are handled for free because the >= comparisons never produce the same ordering twice.

Companies that ask Next Permutation

Next Permutation is tagged by 126 companies in our interview dataset. The score shows how often it comes up at each company.

and 102 more.

Get live help in the real interview

Working solutions in real time during your actual interview. Invisible to screensharing.

Start Free Trial

No credit card required

Problem

Constraints

Practice

How to solve Next Permutation

Approach 1: Generate every ordering

Approach 2: Find the pivot, then sort the tail

Approach 3: Pivot, swap, reverse

Solution code

Common mistakes

What interviewers look for

Follow-up questions

How would you find the previous permutation instead?

How do you find the k-th permutation of 1..n directly?

How would you list every distinct permutation in order?

Companies that ask Next Permutation

Practice next

Get live help in the real interview

Problem

Constraints

Practice

How to solve Next Permutation

Approach 1: Generate every ordering

Approach 2: Find the pivot, then sort the tail

Approach 3: Pivot, swap, reverse

Solution code

Common mistakes

What interviewers look for

Follow-up questions

How would you find the previous permutation instead?

How do you find the k-th permutation of 1..n directly?

How would you list every distinct permutation in order?

Companies that ask Next Permutation

Practice next

Get live help in the real interview