Rearrange a sequence into the next greater permutation in lexicographic order
Company: Microsoft
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: hard
Interview Round: Onsite
Given a list of integers, rearrange it into the next arrangement in lexicographic order: the smallest arrangement of the same values that is strictly greater than the current one. If no greater arrangement exists, return the smallest arrangement instead. The report describes this round as a variant of the classic next-permutation problem without saying what the variant changed; this is the base problem.
### Function Signature
```python
def next_arrangement(nums: list[int]) -> list[int]:
```
### Rules
- Arrangements are compared lexicographically: the first position where two lists differ decides which one is greater.
- Values may repeat. The result contains exactly the same values as `nums`, with the same multiplicities.
- If `nums` is already the greatest arrangement (its values are in non-increasing order), return the values in non-decreasing order.
- Return the rearranged list. Modifying `nums` in place and returning it is acceptable.
### Constraints
- `1 <= len(nums) <= 10^5`
- `0 <= nums[i] <= 10^9`
### Examples
**Example 1**
```text
Input: nums = [2, 3, 1]
Output: [3, 1, 2]
```
In order, the arrangements of `1, 2, 3` are `123, 132, 213, 231, 312, 321`; the one after `231` is `312`.
**Example 2**
```text
Input: nums = [1, 5, 5, 2]
Output: [2, 1, 5, 5]
```
`1552` is the greatest arrangement that starts with `1`, so the next one is the smallest arrangement that starts with `2`.
**Example 3**
```text
Input: nums = [4, 4, 3, 1]
Output: [1, 3, 4, 4]
```
The values are in non-increasing order, so no greater arrangement exists and the smallest one is returned.
Overview: Rearrange a list of integers into the next greater arrangement of the same values in lexicographic order, wrapping around to the smallest arrangement when none is greater. It tests reasoning about lexicographic order, duplicate values and in-place array manipulation.
Given a list of integers `nums`, rearrange it into the next arrangement in lexicographic order: the smallest arrangement of the same values that is strictly greater than the current one. If no greater arrangement exists, return the smallest arrangement instead.
Implement `next_arrangement(nums)` and return the rearranged list.
### Rules
- Arrangements are compared lexicographically: the first position where two lists differ decides which one is greater.
- Values may repeat. The result contains exactly the same values as `nums`, with the same multiplicities.
- If `nums` is already the greatest arrangement (its values are in non-increasing order), return the values in non-decreasing order.
- Return the rearranged list. Modifying `nums` in place and returning it is acceptable.
### Constraints
- `1 <= len(nums) <= 10^5`
- `0 <= nums[i] <= 10^9`
- No value exceeds 2^31 - 1, so every value fits in a signed 32-bit integer (Java `int`, C++ `int`).
### Examples
**Example 1**
```text
Input: nums = [2, 3, 1]
Output: [3, 1, 2]
```
In order, the arrangements of `1, 2, 3` are `123, 132, 213, 231, 312, 321`; the one after `231` is `312`.
**Example 2**
```text
Input: nums = [1, 5, 5, 2]
Output: [2, 1, 5, 5]
```
`1552` is the greatest arrangement that starts with `1`, so the next one is the smallest arrangement that starts with `2`.
Constraints
- 1 <= len(nums) <= 10^5
- 0 <= nums[i] <= 10^9
- Values may repeat; the result has the same values with the same multiplicities.
- No value exceeds 2^31 - 1, so 32-bit integers suffice in every language.
Examples
Input: ([7],)
Expected Output: [7]
Explanation: Singleton (minimum length): it is already the greatest arrangement, so the smallest arrangement is the same list.
Input: ([5, 5, 5, 5],)
Expected Output: [5, 5, 5, 5]
Explanation: All values equal: only one arrangement exists, so the same list comes back.
Hints
- Lexicographic order is decided by the first differing position, so the smallest possible increase keeps as long a prefix of nums unchanged as it can.
- Example 2 shows that when the values after some position are already in their greatest order, the next arrangement has to change an earlier position.
- Because values repeat and the result must be strictly greater, exchanging two equal values never helps.