Next Permutation

Next Permutation

What is this problem about?

The Next Permutation problem asks you to rearrange an array of integers into the lexicographically next greater permutation in-place. If no such permutation exists (the array is already the largest permutation), rearrange it to the smallest permutation (ascending order). This Next Permutation coding problem is one of the most important two-pointer algorithms to master for interviews.

Why is this asked in interviews?

J.P. Morgan, Apple, Goldman Sachs, Microsoft, Meta, Amazon, Google, Bloomberg, Adobe, and dozens more ask this because it's a fundamental combinatorics algorithm used in permutation generators, combinatorial optimization, and sequence problems. The array and two pointers interview pattern is the core, and the three-step algorithm is both elegant and non-trivial.

Algorithmic pattern used

Three-step two-pointer algorithm:

1. Find the rightmost "descent": scan from right to find index i where arr[i] < arr[i+1].
2. If found, swap arr[i] with the rightmost element greater than arr[i] (scan from right).
3. Reverse the suffix starting at index i+1. If no descent found (all descending), reverse the entire array.

Example explanation

Array: [1, 5, 3, 4, 2].

• Step 1: Rightmost descent at index 1 (5 > 3 > 4... wait: arr[2]=3 < arr[3]=4, so descent at i=2? Let's redo: from right: arr[3]=4 > arr[4]=2 (no descent right-to-left), arr[2]=3 < arr[3]=4 (descent!). i=2.
• Step 2: Rightmost element > arr[2]=3 in suffix [4,2]: that's 4 at index 3. Swap: [1,5,4,3,2].
• Step 3: Reverse suffix after i=2: reverse [3,2] → [2,3]. Result: [1,5,4,2,3].

Common mistakes candidates make

• Searching for the descent from the left instead of the right.
• Swapping with the leftmost (not rightmost) element greater than the pivot.
• Forgetting to reverse the suffix after swapping (not just the two swapped elements).
• Not handling the all-descending case (must fully reverse).

Interview preparation tip

Next Permutation has three precisely ordered steps — memorize them as a unit. The common way to remember: "find the last 'valley', swap with the next larger from right, sort the tail." The "sort the tail" is always a reverse because the tail is already descending. Practice implementing this until it takes under 5 minutes. It's the foundation for permutation-based problems including Next Permutation variants, permutation ranking, and k-th permutation problems.