Generate the next lexicographic array arrangement

Given an integer array nums (which may include negative numbers and duplicates), modify nums in place to produce the next arrangement in lexicographic order relative to the current arrangement. If no greater arrangement exists (the array is in strictly descending / non-increasing order), rearrange it into the smallest possible order (sorted ascending). Aim for O(n) time and O(1) extra space.

Be ready to address all of the following:

1. Describe and implement the in-place algorithm that produces the next lexicographic arrangement.
2. Prove its correctness (why the chosen pivot and swap-then-reverse produces exactly the next-greater arrangement, and why none is skipped).
3. Handle edge cases explicitly: arrays with duplicate values, strictly descending arrays (no next arrangement), single-element and empty arrays.
4. Confirm the approach works unchanged when the array contains negative numbers.
5. Follow-up: generalize the ordering to a custom comparator so the "next arrangement" is defined by an arbitrary total order rather than natural integer order.
6. Discuss practical considerations for very large arrays (e.g., cache behavior / sequential access) and provide a set of tests.

What a Strong Answer Covers

• A clear algorithm with the right data structures and enough pseudocode or code-level detail to implement it.
• A correctness argument that explains why the algorithm covers all required cases.
• Time and space complexity, plus at least one alternative approach when relevant.
• Focused tests for normal cases, edge cases, and failure modes.

Follow-up Questions

• How would the approach change if the input were streaming or too large for memory?
• What invariants would you assert in production code?
• Which tests would catch off-by-one, duplicate, or tie-breaking bugs?

Generate the next lexicographic array arrangement

Given an integer array nums (which may include negative numbers and duplicates), modify nums in place to produce the next arrangement in lexicographic order relative to the current arrangement. If no greater arrangement exists (the array is in strictly descending / non-increasing order), rearrange it into the smallest possible order (sorted ascending).

This is the classic next permutation problem. Aim for O(n) time and O(1) extra space.

In this console the function returns the modified array so the result can be checked, but the intended algorithm rearranges nums in place.

Examples

• [1, 2, 3] -> [1, 3, 2]
• [3, 2, 1] -> [1, 2, 3] (already the largest, wraps to the smallest)
• [1, 1, 5] -> [1, 5, 1] (duplicates handled by strict comparisons)

Algorithm

1. Find the pivot: the rightmost index i with nums[i] < nums[i+1].
2. If a pivot exists, find the rightmost j > i with nums[j] > nums[i] and swap nums[i], nums[j].
3. Reverse the suffix nums[i+1:] (it is non-increasing, so reversing makes it the smallest tail).
4. If no pivot exists, the array is the last arrangement; reversing the whole array yields the smallest.

Constraints

• 0 <= len(nums) <= 10^5
• -10^9 <= nums[i] <= 10^9
• nums may contain duplicate values
• Must run in O(n) time and O(1) extra space (in-place rearrangement)

Hints

1. Scan from the right to find the first index i where nums[i] < nums[i+1]. Everything to the right of i is already in non-increasing (maximal) order.
2. To make the smallest possible increase, swap nums[i] with the smallest element to its right that is still strictly greater than nums[i].
3. After the swap, the suffix to the right of i is still non-increasing, so reverse it to get the smallest tail. If no pivot i exists, reverse the entire array.

Solution

Single-pass next-permutation: find the rightmost ascending pivot from the right, swap it with the smallest suffix element that is still larger, then reverse the suffix. O(n) time, O(1) space. Strict comparisons handle duplicates; the comparisons are value-only so negatives work unchanged; routing comparisons through a comparator generalizes the ordering. No pivot means the array is the last arrangement, so reversing yields the smallest.

Solution Alignment

The improved prompt asks for a structured answer that states assumptions, covers edge cases, and explains trade-offs. The answer below preserves the original solution content while making the expected interview coverage explicit.

Interview Framing

• Start by restating the goal and the assumptions you need.
• Work through the main approach in the same order as the prompt.
• Call out trade-offs, edge cases, and validation steps before finalizing the recommendation.

Detailed Answer

This is the classic next-permutation problem. The standard algorithm runs in a single in-place pass: O(n) time, O(1) extra space.

Algorithm

1. Find the pivot. Scan from the right and find the largest index i such that nums[i] < nums[i+1]. This is the rightmost element that can be increased. If no such i exists, the array is non-increasing — it is the last arrangement — so go to step 4 (just reverse the whole array to get the smallest).
2. Find the successor. Scan from the right and find the largest index j > i such that nums[j] > nums[i]. Because the suffix after i is non-increasing, nums[j] is the smallest element in that suffix that is still strictly greater than the pivot.
3. Swap nums[i] and nums[j].
4. Reverse the suffix to the right of index i (i.e. nums[i+1 .. end]). The suffix was non-increasing; after the swap it remains non-increasing, so reversing it makes it ascending — the smallest possible tail given the increased prefix.

Why it is correct

• The suffix starting at i+1 is, by the choice of i, the longest non-increasing suffix — it is already the maximum arrangement of those elements and cannot be advanced internally. The only way to get a larger overall arrangement is to increase position i.
• To increase position i by the smallest amount, we put at i the smallest suffix element strictly greater than nums[i] — that is nums[j] (step 2). After the swap, the suffix is still non-increasing, so the smallest completion of the new prefix is the ascending order of the suffix — obtained by reversing it (step 4). Producing the smallest legal increase at the rightmost possible position is exactly the definition of the next arrangement, so nothing is skipped.
• When step 1 finds no pivot, the array is the maximum arrangement; reversing it yields the sorted-ascending (minimum) arrangement, satisfying the wrap-around requirement.

Duplicates and negative numbers

• Duplicates: Using strict inequalities (< in step 1, > in step 2) is what makes duplicates correct. The comparisons are value-based, so equal elements never trigger a spurious pivot and the algorithm produces each distinct arrangement once. No special handling is required.
• Negative numbers: The algorithm only compares element values; it never assumes non-negativity or indexes by value. Negative numbers therefore work with no changes.

Edge cases

• Empty array or single element: no pivot exists; the (vacuous) reverse leaves it unchanged.
• Strictly descending, e.g. [3,2,1] -> reverse -> [1,2,3].
• All equal, e.g. [2,2,2]: no strict pivot -> reversed -> unchanged (only one arrangement).

Reference implementation (Python)

from typing import List, Callable

def next_permutation(nums: List[int]) -> None:
    """Modify nums in place to the next lexicographic arrangement.
    If none exists, rearrange to the smallest (ascending) order."""
    n = len(nums)
    # 1) find pivot: rightmost i with nums[i] < nums[i+1]
    i = n - 2
    while i >= 0 and nums[i] >= nums[i + 1]:
        i -= 1
    if i >= 0:
        # 2) find rightmost j > i with nums[j] > nums[i]
        j = n - 1
        while nums[j] <= nums[i]:
            j -= 1
        # 3) swap
        nums[i], nums[j] = nums[j], nums[i]
    # 4) reverse the suffix nums[i+1:]
    lo, hi = i + 1, n - 1
    while lo < hi:
        nums[lo], nums[hi] = nums[hi], nums[lo]
        lo += 1
        hi -= 1

Follow-up: custom comparator

Factor the two value comparisons (steps 1 and 2) and the suffix reversal through a comparator cmp(a, b) that returns negative / 0 / positive, defining an arbitrary total order. "Lexicographic" is then defined with respect to that order. Time and space are unchanged.

def next_permutation_cmp(nums: List[int], cmp: Callable[[int, int], int]) -> None:
    n = len(nums)
    i = n - 2
    while i >= 0 and cmp(nums[i], nums[i + 1]) >= 0:   # nums[i] not < nums[i+1]
        i -= 1
    if i >= 0:
        j = n - 1
        while cmp(nums[j], nums[i]) <= 0:               # find smallest > pivot
            j -= 1
        nums[i], nums[j] = nums[j], nums[i]
    lo, hi = i + 1, n - 1
    while lo < hi:
        nums[lo], nums[hi] = nums[hi], nums[lo]
        lo += 1
        hi -= 1

Large arrays / practical considerations

• The algorithm makes at most two right-to-left scans plus one suffix reversal, all sequential memory accesses — cache- and prefetch-friendly, with no extra allocation.
• It is in place, so memory bandwidth, not auxiliary space, is the constraint; performance is dominated by the (typically short) suffix.
• For repeatedly enumerating all permutations, call next_permutation in a loop until it wraps back to the sorted order; each call is amortized O(1) in practice but O(n) worst case.

Tests

def _run(a):
    next_permutation(a)
    return a

assert _run([1, 2, 3]) == [1, 3, 2]          # basic next
assert _run([3, 2, 1]) == [1, 2, 3]          # descending -> smallest
assert _run([1, 1, 5]) == [1, 5, 1]          # duplicates
assert _run([2, 2, 2]) == [2, 2, 2]          # all equal -> unchanged
assert _run([-1, 0, -3]) == [0, -3, -1]      # negatives
assert _run([1]) == [1]                       # single element
assert _run([]) == []                         # empty

Checks and Follow-ups

• Verify that the answer addresses every requested part of the prompt.
• Identify the highest-risk assumption and explain how you would validate it.
• Be ready to discuss an alternative approach and why you did not choose it first.

An in-place O(n)-time, O(1)-space implementation that returns the next lexicographic arrangement, falls back to the sorted-ascending arrangement when none exists, correctly handles duplicates, negative numbers, and degenerate inputs (empty / single-element / all-equal / strictly descending), with a correctness argument and a generalization to a custom comparator.