Generate the next lexicographic array arrangement
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Onsite
##### Question
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.
Quick Answer: This interview question evaluates algorithm design, data structures, correctness, complexity, edge cases, and implementation details in a realistic interview setting. A strong answer for Generate the next lexicographic array arrangement states assumptions, handles edge cases, explains trade-offs, and shows how to validate the result clearly.
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)
Examples
Input: ([1, 2, 3],)
Expected Output: [1, 3, 2]
Explanation: Pivot at i=1 (2<3); swap with 3 then reverse the 1-element suffix -> [1,3,2].
Input: ([3, 2, 1],)
Expected Output: [1, 2, 3]
Explanation: Strictly descending: no pivot, so reverse the whole array to the smallest arrangement.
Hints
- 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.
- To make the smallest possible increase, swap nums[i] with the smallest element to its right that is still strictly greater than nums[i].
- 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.