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

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

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

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

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].