Skip to main content

31. Next Permutation

medium

Rearrange an array into the lexicographically next greater permutation, in place. Famous for a beautifully concise algorithm: find pivot, find swap target, swap, reverse suffix.

By Alex Chen, Founder, InterviewChamp.AI · Last verified

Problem

Given an array of integers nums, find the next permutation of nums. The replacement must be in place and use only constant extra memory. The next permutation of an array of integers is the next lexicographically greater permutation of its integer values. If such an arrangement is not possible (the array is in descending order), the array must be rearranged into the lowest possible order (sorted in ascending order).

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: Already the largest permutation, so wrap around to the smallest.

Example 3

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

Solve it now

Free. No sign-up. Python and JavaScript run instantly in your browser.

Output

Press Run or Cmd+Enter to execute

Hints

Progressive — try the first before opening the next.

Hint 1

Scan from the right. The longest non-increasing suffix is already 'maxed out' — you can't improve the permutation by reordering it alone.

Hint 2

Find the first index i (from the right) where nums[i] < nums[i+1]. That nums[i] is your pivot.

Hint 3

Find the rightmost element in the suffix that is greater than the pivot, swap them, then reverse the suffix to make it ascending. If no pivot exists (array fully non-increasing), reverse the whole array.

Solution approach

Reveal approach

Four steps. Step 1: walk from the right to find the first index i where nums[i] < nums[i+1]. This is the pivot — everything to its right is non-increasing and already the largest arrangement of those elements. Step 2: if no pivot exists, the entire array is the largest permutation; reverse it to get the smallest and return. Step 3: walk from the right again to find the smallest element greater than the pivot (the rightmost element greater than nums[i], because the suffix is sorted in descending order). Swap it with the pivot. Step 4: reverse the suffix to the right of position i — this turns the still-descending suffix into the smallest ascending arrangement, which is the minimal increment over the pivot swap. The result is the next permutation in lexicographic order, computed in O(n) time and O(1) space.

Complexity

Time
O(n)
Space
O(1)

Related patterns

  • two-pointers
  • in-place

Related problems

Asked at

Companies reported asking this problem (sourced from public Glassdoor, Blind, and Levels.fyi interview posts).

  • Meta
  • Google
  • Amazon
  • Microsoft
  • Apple

Practice these live with InterviewChamp.AI

Drill Next Permutation and Arrays problems under real interview conditions with instant feedback on your reasoning, complexity claims, and code.

Practice these live with InterviewChamp.AI →