Next Permutation
Crack a combination lock, one arrangement at a time. The wheels show the numbers in nums. You try every arrangement of those same numbers in dictionary order: compare the first numbers, then the second, and so on. Return the arrangement that comes right after nums. If nums is already the very last one, wrap around and return the first one, with the numbers rising. Repeated numbers are allowed, and swapping two equal numbers is not a new arrangement. Limits: 1 to 500,000 numbers, each from 0 to 1,000,000,000. Think about: how many arrangements are there, and how many could you afford to try? Example (wheels 4, 2, 6, 5, 3, 1): the tail 6, 5, 3, 1 is already as big as it can be, so the 2 in front of it has to grow the smallest number in the tail that is bigger than 2 is 3, and it takes the 2's place the leftovers 2, 6, 5, 1 go behind it in their smallest order: 1, 2, 5, 6 full answer: [4, 3, 1, 2, 5, 6]
You're stepping a combination lock forward by one: given the arrangement it shows now, which arrangement of the same numbers comes next in dictionary order? Interviewers love it because no library call saves you, and repeated numbers or a lock that is already on its last arrangement punish sloppy reasoning. The classic trap is trying every arrangement, which explodes fast. You get 1 to 500,000 numbers, each from 0 to 1,000,000,000.
Examples
You write
next_permutation(nums: List[int])
Example 1
- Input
- nums = [4,2,6,5,3,1]
- returns
- [4,3,1,2,5,6]
Example 2
- Input
- nums = [9,5,4,1]
- returns
- [1,4,5,9]
Save this for your laptop
The editor and Run need a bigger screen. The link opens Next Permutation ready to code. It is free, and the editor needs no account.
The pattern behind it
Arrays & Hashing
I reach for it when
- You catch yourself scanning the array again for every element.
- The problem asks about duplicates, pairs, counts or groups.
Say this before you type. Say what the key is and what the value remembers, before you write the loop.
All 126 Arrays & Hashing problemsTwo Pointers
I reach for it when
- The array is sorted, or you can sort it.
- You need a pair, a triple or a palindrome.
Say this before you type. Say what each pointer means and what a move to the left or right rules out.
All 26 Two Pointers problems
Meet Coco
Coco is an AI study partner, not a person. She listens while you explain your code, asks what a line does and never hands you the fix. Sign in free to type with Coco, up to a daily limit, and to talk with her for one hour. After that, talking comes with the $79 pack. Anyone can open the editor and run their code.