AlgoViz
HomeArrays & Hashing

Next Permutation

Medium

Find the pivot, swap the successor, reverse the tail

Problem

A permutation of an array of integers is an arrangement of its members into a sequence or linear order. For example, for arr = [1,2,3], the following are all the permutations of arr: [1,2,3], [1,3,2], [2,1,3], [2,3,1], [3,1,2], [3,2,1]. The next permutation of an array of integers is the next lexicographically greater permutation of its integers. More formally, if all the permutations of the array are sorted in lexicographical order, then the next permutation of that array is the permutation that follows it in the sorted order. If such arrangement is not possible (i.e., the array is the last permutation), then rearrange it to the lowest possible order (i.e., sorted in ascending order). You must rearrange the numbers in-place and use only constant extra memory.

In simple words

Find the rightmost rising step, swap it with the next-bigger digit to its right, then sort the tail up.

The idea

Scan from the right for the first index where nums[i] < nums[i+1] — that pivot is the only place a change can make the number bigger by the smallest amount. Swap it with the smallest value to its right that still exceeds it, then reverse the suffix, which is descending and so becomes the smallest possible tail.

The trick

  • The suffix after the pivot is always non-increasing — that is why reversing sorts it.
  • No pivot means the array is the last permutation; reverse the whole thing.
  • O(n) time, O(1) space.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
3
0
1
2

Step 1 of 2. Here's the example — nums = [1,2,3] Values: 1, 2, 3.

1/2
Optimal
timeO(n)spaceO(1)
1// 1. find rightmost i with nums[i] < nums[i+1]2i = n - 23while i >= 0 and nums[i] >= nums[i+1]: i--4// 2. if found, swap with its next-greater to the right5if i >= 0:6  j = n - 17  while nums[j] <= nums[i]: j--8  swap(nums[i], nums[j])9// 3. reverse the suffix after i10reverse(nums, i+1, n-1)

Input

array
[1, 2, 3]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
nums = [1, 2, 3]
Output:
[1, 3, 2]
Explanation:
The next bigger arrangement is 1,3,2.

Example 2

Input:
nums = [3, 2, 1]
Output:
[1, 2, 3]
Explanation:
Already the largest, so wrap to the smallest.

Example 3

Input:
nums = [1, 1, 5]
Output:
[1, 5, 1]
Explanation:
Swap to get 1,5,1.

Constraints

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

Practice this problem:LeetCode(opens in a new tab)Search GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.