MediumCoding

Next Permutation

Asked at

Nvidia

1Give yourself 5 minutes

2Answer out loud, not in your head

3Then compare with the answer below

The 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.

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

Input: nums = [3,2,1] Output: [1,2,3] **Explanation: ** [3,2,1] is the last permutation. So we return the first: [1,2,3].

Input: nums = [1,1,5]

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

cpp

class Solution {
public:
    void nextPermutation(vector<int>& nums) {
        // Your code goes here
    }
};

java

class Solution {
    public void nextPermutation(int[] nums) {
        // Your code goes here
    }
}

python

class Solution:
    def nextPermutation(self, nums):
        # Your code goes here

javascript

class Solution {
    nextPermutation(nums) {
        // Your code goes here
    }
}

csharp

public class Solution {
    public void NextPermutation(List<int> nums) {
        // Your code goes here
    }
}

func nextPermutation(nums []int) {
	//your code goes here
}

Solve on LeetCode →

Stuck? Show a way to structure it+

01Find rightmost ascending pivot
02Handle fully descending case
03Find rightmost successor greater than pivot
04Swap them
05Reverse decreasing suffix

Reference answer

Make the smallest lexicographic increase

Walk from the right until finding the first index i with a[i] < a[i+1]. Everything to its right is nonincreasing. If no pivot exists, the sequence is the largest permutation, so reverse all values to obtain the smallest. Otherwise scan from the right for the first value greater than a[i], swap it with the pivot, then reverse the suffix.

Choosing the rightmost pivot preserves the longest possible prefix. Choosing the rightmost greater successor makes the increase minimal even with duplicates. The suffix was nonincreasing before the swap, so reversing it produces its smallest order in linear time. Total runtime is O(n) and extra space is O(1). Test one element, already descending input, already ascending input, repeated values such as [1,5,1], and a pivot immediately before the final element. Sorting the suffix works but costs O(n log n) and misses the useful invariant.

Then expect these follow-ups

Why is the suffix decreasing before reversal?
Tests: correctness reasoning
How do duplicates affect successor choice?
Tests: follow-up reasoning

Free to read · better with Enzo

Practice this out loud with Enzo

Enzo runs it as a mock interview, pushes back with follow-ups, and grades you on the rubric.

Continue with Enzo Sign up free

Next question