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

Next Lexicographic Arrangement of an Integer Array

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

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 = [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.

Hints

1. 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.
2. 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.
3. 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.

Approach

Scan from the right for the pivot: the largest index i with nums[i] < nums[i + 1]. Everything after i is non-increasing, so that suffix is already the largest arrangement of its own values and no change confined to it can make the array greater; i is therefore the rightmost position that can be increased, and keeping the longest possible prefix unchanged yields the smallest greater arrangement. If no pivot exists, the whole array is non-increasing, which is exactly the largest arrangement, and reversing it gives the ascending (smallest) arrangement as required. Otherwise swap nums[i] with the rightmost suffix element strictly greater than nums[i]: because the suffix is non-increasing, that element holds the smallest value larger than nums[i], and taking its rightmost copy keeps the suffix non-increasing after the swap. Finally reverse the suffix so it becomes non-decreasing, its smallest arrangement. The comparisons are strict in the right places (skip while nums[i] >= nums[i + 1] when finding the pivot, skip while nums[j] <= nums[i] when choosing the swap partner), so swapping equal values is never mistaken for a new arrangement and duplicates are handled correctly. Edge cases: a length-1 array has no pivot and is returned unchanged; an all-equal array has no pivot and reverses to itself; values stay within 32-bit range and no arithmetic beyond comparison is performed.

• Time complexity: O(n)
• Space complexity: O(n)