Coding Interview: Compute the Next Permutation In Place

What the interviewer evaluates

Given an integer array that may contain duplicates, mutate it into the next strictly larger lexicographic permutation in place; if the current order is maximal, produce the smallest ascending permutation.

Constraints and boundaries

• Use O(1) extra space and only swaps or reversals.
• Duplicate values are not distinct identities, but comparisons are numeric.
• Empty and one-element arrays remain unchanged.
• The result must be the globally adjacent lexicographic permutation, not an arbitrary local swap.

Find the rightmost pivot

Scan from the right for the first index i where the left value is strictly less than the right value. The suffix is already non-increasing. If no pivot exists, the whole array is maximal; reverse it to obtain the minimum permutation.

Swap and minimize the suffix

With a pivot, scan from the right for the first value greater than nums[i]. Because the suffix is non-increasing, that first candidate is the smallest feasible larger value. Swap it with the pivot, then reverse the suffix after i to make it ascending.

30-second answer framework

“Scan from the right for the first increasing pivot i. If none exists, reverse the maximal descending array. Otherwise find the rightmost value greater than nums[i], swap them, and reverse the suffix. The suffix starts ordered in the opposite direction, so this makes the smallest possible increase in O(n) time and O(1) space.”

Clarifying questions before answering

• Must the mutation be in place? Extra space would allow sorting a copy, while in-place requires reversal.
• Is lexicographic order numeric or string-based? Negative and multi-digit values differ.
• Can values repeat? Duplicates require strict comparisons for both pivot and swap candidate.

Step-by-step deep dive

For [1,2,3], pivot at 1 swaps with the smallest larger suffix value 2, leaving [2,1,3] after suffix reversal. For [3,2,1], no pivot exists, so reversal produces [1,2,3].

i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
    i -= 1
if i >= 0:
    j = n - 1
    while nums[j] <= nums[i]:
        j -= 1
    swap(nums[i], nums[j])
reverse(nums, i + 1, n - 1)

Use “greater than or equal” while skipping pivot candidates and “less than or equal” while skipping swap candidates, ensuring a strict increase. Reverse rather than sort because the suffix is already ordered, so reversal stays linear and in place.

Model high-quality answer

“The next permutation changes the rightmost possible position and makes everything after it as small as possible. I find the rightmost pivot where the left value is strictly less than the right value, swap it with the rightmost value greater than it, and reverse the suffix. No pivot means the array is maximal, so I reverse the whole array. Scans and reversal are O(n) and the algorithm uses constant extra variables.”

Common mistakes

• Finding the pivot from the left and changing a higher-order position.
• Stopping after the swap without minimizing the suffix.
• Using greater-or-equal for the swap candidate, so duplicates fail to increase strictly.
• Calling a general sort on the suffix and violating the in-place constraint.
• Returning a descending array unchanged when it should wrap to the minimum order.

Failure symptoms and fixes

If [1,3,2] becomes [3,1,2], the pivot is too far left; the correct result is [2,1,3]. If [1,1,5] swaps equal values, the strict comparison boundary is wrong.

Production implementation

Accept a mutable random-access sequence and reverse with two pointers. If comparison can overflow or language ordering differs, define the comparator and invalid-input policy at the interface boundary.

Verification checklist

Test empty, one element, ascending, descending, duplicates, a pivot at the end, and multiple equal optima. For small arrays, generate all distinct permutations, sort them lexicographically, and verify that the function returns the next item or wraps to the first.

Follow-up questions and answers

Why must the pivot be the rightmost one?

A farther-right pivot changes a lower-order position. Choosing the smallest feasible larger value and minimizing its suffix therefore yields the adjacent permutation rather than skipping valid orders.

Why can the suffix be reversed directly?

The right-to-left pivot scan proves the suffix is non-increasing. After the swap, reversing it restores the smallest ascending order without a general sort.

What about the kth next permutation?

Repeating the operation costs O(k n). For large k, rank/unrank or counting approaches may jump directly, but they require combinatorial counting and duplicate handling.

Scoring rubric

• Pivot: finds the rightmost strict ascent.
• Swap: chooses the first strict larger value from the right.
• Suffix: reverses it into the smallest ascending order.
• Boundaries: covers descending, duplicates, empty, and one-element arrays.
• Complexity: gives O(n) time and O(1) extra space.

Compliance check

Confirm that the three steps, boundary examples, and complexity claim stay consistent.

Interview answer checklist

Explain the smallest right-side change, write pivot, swap, and reverse, use a duplicate example for strict comparisons, then give complexity and exhaustive small-permutation testing.

One-sentence takeaway

The next permutation is found in place by the rightmost pivot, the smallest feasible larger swap, and a suffix reversal in linear time.