Katkat
Back

Generate the next lexicographic array arrangement

DoorDashSoftware Engineer · Onsite
MediumSoftware EngineerOnsiteCoding & Algorithms

Last updated

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.

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.