Rearrange an Integer Array into Its Next Lexicographic Arrangement
Company: Oracle
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Technical Screen
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]`.
Overview: A coding problem that asks you to rearrange an integer array into the next lexicographically greater arrangement of its values, wrapping around to ascending order when the array is already the largest. It tests reasoning about lexicographic order, repeated values and complexity analysis.
Given an array of integers `nums`, return its next arrangement: the smallest arrangement (reordering) of the same values that is lexicographically greater than `nums`. If no greater arrangement exists, because `nums` is already the largest arrangement of its values, return the smallest arrangement instead, which is the values in ascending order.
The interviewer also asked you to explain the approach in detail and to analyze its time and space complexity.
### 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.
### 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 = [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]`. (Likewise `[3, 2, 1]` is the largest arrangement of its values, so its result wraps around to `[1, 2, 3]`.)
### Constraints
- `1 <= len(nums) <= 10^5`
- `-10^9 <= nums[i] <= 10^9`
- Every value fits in a signed 32-bit integer (no value exceeds 2^31-1), so Java uses `int` and C++ uses `int`.
Constraints
- 1 <= len(nums) <= 10^5
- -10^9 <= nums[i] <= 10^9
- Every value fits in a signed 32-bit integer (no value exceeds 2^31-1).
Examples
Input: ([7],)
Expected Output: [7]
Explanation: Length 1 is both smallest and largest, so it is returned unchanged.
Input: ([1, 3, 2],)
Expected Output: [2, 1, 3]
Explanation: Source example 1: the arrangement after [1, 3, 2] is [2, 1, 3].
Hints
- Lexicographic order is decided by the first index where two arrangements differ, so the smallest greater arrangement shares as long a prefix with nums as possible.
- Think about what nums looks like when it is already the largest arrangement of its values, and what the smallest arrangement of the same values looks like.
- With repeated values, exchanging two equal values does not create a new arrangement; make sure your result is strictly greater whenever a greater arrangement exists.