Generate the next lexicographic array arrangement
Company: DoorDash
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: Medium
Interview Round: Onsite
Given an integer array nums that may include negative numbers and duplicates, modify nums in place to produce the next sequence in lexicographic order. If no such sequence exists, rearrange nums into the smallest possible order. Achieve O(n) time and O(
1) extra space. Explain edge cases (e.g., repeated values, strictly descending arrays) and prove correctness. Discuss practical considerations for very large arrays (e.g., cache behavior) and provide tests.
Quick Answer: This question evaluates array-manipulation and permutation-generation skills, including in-place modification, handling negative numbers and duplicates, algorithmic invariants, and meeting O(n) time and O(1) extra space constraints within the Coding & Algorithms domain.