Rearrange an Integer Array into Its Next Lexicographic Arrangement

Given an array of integers `nums`, rearrange it into its next arrangement: the smallest arrangement of the same values that is lexicographically greater than `nums`. If no greater arrangement exists, because `nums` is already the largest one, return the smallest arrangement instead, which is the values in ascending order. The interviewer asked for three things in order: explain the approach in detail, implement it, and analyze its time and space complexity. ### Function Signature ```python def next_arrangement(nums: list[int]) -> list[int]: ``` ### Rules - Arrangements are compared lexicographically: the first index at which two arrangements differ decides, and the arrangement with the smaller value at that index is smaller. - With repeated values, arrangements that are equal as sequences are the same arrangement, so the result is strictly greater than `nums` unless `nums` is the largest arrangement. - An array of length 1 is both the smallest and the largest arrangement, so it is returned unchanged. - Return the resulting array. Rearranging `nums` in place and returning it is allowed. ### Constraints - `1 <= len(nums) <= 10^5` - `-10^9 <= nums[i] <= 10^9` ### Examples **Example 1** ```text Input: nums = [1, 3, 2] Output: [2, 1, 3] ``` In increasing order, the arrangements of `1, 2, 3` are `[1, 2, 3]`, `[1, 3, 2]`, `[2, 1, 3]`, and so on, so the one after `[1, 3, 2]` is `[2, 1, 3]`. **Example 2** ```text Input: nums = [3, 2, 1] Output: [1, 2, 3] ``` `[3, 2, 1]` is the largest arrangement, so the result wraps around to the smallest. **Example 3** ```text Input: nums = [1, 5, 1] Output: [5, 1, 1] ``` The distinct arrangements of `1, 1, 5` in increasing order are `[1, 1, 5]`, `[1, 5, 1]` and `[5, 1, 1]`.