PPractick

The problem

A lock-cracking training game shows the digits of a combination and asks for the next combination in dictionary order using the same digits. If the digits are already in their largest arrangement (like 3 2 1), it wraps around to the smallest (1 2 3). Generating all permutations and sorting them is hopeless for even ten digits. The classic in-place algorithm finds the answer in O(n) by looking from the right for the first place where the digits stop increasing.

Example: [1, 2, 3] → [1, 3, 2]; [3, 2, 1] → [1, 2, 3].

Function signature

void nextPermutation(vector<int>& nums);  // in place; wraps to the smallest permutation after the largest

Test cases

Input nums	Output	Explanation
[1, 2, 3]	[1, 3, 2]
[3, 2, 1]	[1, 2, 3]	Last permutation wraps to the first
[1, 1, 5]	[1, 5, 1]	Duplicates
[1, 3, 2]	[2, 1, 3]
[2, 3, 1]	[3, 1, 2]
[1]	[1]

(Confirm: in place with O(1) extra space; the behaviour matches std::next_permutation, which the code cross-checks on random arrays.)

How interviewers phrase it

• "Implement next permutation" (LeetCode 31).
• "Find the next greater number using the same digits" (LeetCode 556 is the integer version).
• "Generate permutations in lexicographic order."

Clarifying questions to ask

1. What should happen after the last permutation: wrap to the first?
2. In place, with O(1) extra space?
3. Can there be duplicate values?

Follow-ups to expect

1. "Why look for the first decrease from the right?"
2. "Why swap with the smallest larger element in the suffix?"
3. "Why reverse the suffix afterwards?"
4. "How does it handle duplicates?"
5. "Complexity?"

Related questions

• Sort an array of 0's 1's and 2's Medium
• Rearrange array elements by sign Medium
• 3 Sum Medium
• 4 Sum Medium
• Reverse an array Easy
• Remove duplicates from Sorted array Easy

All 474 dsa interview questions

DSA mock interviews · System design interview questions · Free mock interview practice · Browse interviewers · Sign in