MediumArrayTwo PointersUpdated Sep 2026

31. Next Permutation

Asked at Meta, Microsoft, Bloomberg

Difficulty

Medium

Time

O(n)

Space

O(1)

Pattern

Array

Companies

3

Problem

You are given an array of integers nums. Think of every possible ordering (permutation) of these numbers, sorted from smallest to largest in dictionary order. Your job is to change nums into the ordering that comes right after the current one in that sorted list.

If the current ordering is already the largest possible one, wrap around and change nums into the smallest ordering (numbers sorted in ascending order).

You must do this in place — modify the given array itself. You may only use a constant amount of extra memory, so you cannot build a new array or sort a copy. The function does not return anything; it just changes nums.

Find the next bigger ordering

nums123012Current ordering: [1,2,3]next132012Next ordering: [1,3,2] — the two swapped positions arehighlighted
From [1,2,3] the next ordering in dictionary order is [1,3,2], so that is the answer.

Constraints

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

Examples

Example 1
Inputnums = [1,2,3]
Output[1,3,2]
WhyThe orderings starting with 1 are [1,2,3] then [1,3,2]. So the one right after [1,2,3] is [1,3,2].
Example 2
Inputnums = [3,2,1]
Output[1,2,3]
WhyThis is the largest ordering, so there is nothing bigger. We wrap around to the smallest ordering, which is [1,2,3].
Example 3
Inputnums = [1,1,5]
Output[1,5,1]
WhyThe orderings are [1,1,5], [1,5,1], [5,1,1]. The one right after [1,1,5] is [1,5,1].

Asked At

3 companies
CompanyDifficulty
MetaMediumView all Meta questions →
MicrosoftMediumView all Microsoft questions →
BloombergMediumView all Bloomberg questions →

How to Think About It

1

Scan from right to left to find the first element that is smaller than its right neighbor. This is the "pivot" — the element that needs to be swapped to get a larger permutation.

2

If no pivot exists (array is sorted in descending order), the entire array is the largest permutation. Reverse it to get the smallest.

3

After finding the pivot, find the smallest element to its right that is still larger than the pivot. Swap them. This gives the next larger value at the pivot position.

4

After swapping, reverse the elements to the right of the pivot. This gives the smallest possible suffix, which combined with the new pivot value gives the next permutation.

5

Edge cases: single element (return it), already largest permutation (return smallest), all same elements.

Optimal Approach

Step 1: Find the pivot — scan from right, find first i where nums[i] < nums[i+1].
Step 2: If no pivot, reverse entire array and return.
Step 3: Find the smallest element to the right of pivot that is > pivot.
Step 4: Swap pivot with that element.
Step 5: Reverse the subarray to the right of the pivot position.

Why reverse (not sort) in step 5: after the swap, the suffix is in descending order. Reversing gives ascending order, which is the smallest possible suffix.

Time: O(n) — single pass to find pivot, single pass to find swap target, single pass to reverse. Space: O(1).

Pivot, swap, reverse

nums123012pivotStep 1 — scan from the right: 2 < 3, so index 1 is thepivotnums132012Step 2 — swap pivot 2 with 3, the smallest value toits right that is biggernumssuffix132012Step 3 — reverse the suffix after the pivot; here itis just [2], so nothing changespivot = rightmost i with nums[i] < nums[i+1]swap with smallest larger value on the rightreverse the suffix after the pivot
Find the pivot from the right, swap it with the smallest larger value, then reverse the suffix.
ComplexityTime O(n)Space O(1)We make a few separate left-to-right or right-to-left passes over the array, and each pass touches each element at most once.

What Trips People Up in Real Interviews

1

Not finding the correct pivot. The pivot is the first element from the right that is smaller than its successor. Scanning left to right gives the wrong element.

2

Swapping with the wrong element. After finding the pivot, swap with the smallest element to its right that is still larger than the pivot. Not just any larger element.

3

Sorting the suffix instead of reversing. After the swap, the suffix is already in descending order. Reversing is O(n), sorting is O(n log n). Use reverse.

4

Not handling the all-descending case. If no pivot is found, the array is the largest permutation. Reverse it to get the smallest.

5

Off-by-one in the pivot scan. Scan from n-2 down to 0 (not n-1). The last element can't be a pivot since there's nothing to its right.

Solution Code

O(n) time
def nextPermutation(nums):
    n = len(nums)
    pivot = -1
    for i in range(n - 2, -1, -1):
        if nums[i] < nums[i + 1]:
            pivot = i
            break
    if pivot == -1:
        nums.reverse()
        return
    for j in range(n - 1, pivot, -1):
        if nums[j] > nums[pivot]:
            nums[pivot], nums[j] = nums[j], nums[pivot]
            break
    left, right = pivot + 1, n - 1
    while left < right:
        nums[left], nums[right] = nums[right], nums[left]
        left += 1
        right -= 1

Pro at DSA?

Test your skills with a real FAANG-style mock interview.

Start a Mock Interview →

Frequently Asked Questions

What is the Next Permutation problem?

Rearrange numbers into the lexicographically next greater permutation. If no greater permutation exists, rearrange into the lowest permutation. This problem tests understanding of lexicographic ordering and in-place array manipulation.

How do you solve Next Permutation?

The optimal approach runs in O(n) time and O(1) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.

What companies ask Next Permutation?

Next Permutation is asked at Meta, Microsoft, Bloomberg. It is a medium difficulty problem.

What are common mistakes on Next Permutation?
  • Not finding the correct pivot. The pivot is the first element from the right that is smaller than its successor. Scanning left to right gives the wrong element.
  • Swapping with the wrong element. After finding the pivot, swap with the smallest element to its right that is still larger than the pivot. Not just any larger element.
  • Sorting the suffix instead of reversing. After the swap, the suffix is already in descending order. Reversing is `O(n)`, sorting is `O(n log n)`. Use reverse.
  • Not handling the all-descending case. If no pivot is found, the array is the largest permutation. Reverse it to get the smallest.
  • Off-by-one in the pivot scan. Scan from n-2 down to 0 (not n-1). The last element can't be a pivot since there's nothing to its right.