Next Lexicographical Sequence
Given an array of integers nums representing a permutation, rearrange
it into the next lexicographically greater permutation of its
elements, in place and using only O(1) extra space.
If no such permutation exists (the array is already the highest possible permutation), rearrange it into the lowest possible order (i.e., sorted in ascending order).
Example 1
Input: nums = [1, 2, 3]
Output: [1, 3, 2]
Example 2
Input: nums = [3, 2, 1]
Output: [1, 2, 3]
Explanation: [3, 2, 1] is the highest permutation, so we wrap around
to the lowest one.
Example 3
Input: nums = [1, 1, 5]
Output: [1, 5, 1]
Constraints
1 <= nums.length <= 1000 <= nums[i] <= 100
Think of the array as a number written in digits. To get the very
next larger arrangement, we want to change the smallest possible
suffix. Scan from the right to find the first index i where
nums[i] < nums[i + 1] — everything to the right of i is currently
in non-increasing order (the largest possible arrangement for that
suffix). If no such i exists, the whole array is non-increasing,
meaning it's the last permutation, so we simply reverse it to wrap
around to the first (smallest) permutation.
Otherwise, we want to bump nums[i] up to the smallest value in the
suffix that is still larger than it. Scan from the right again to
find the first index j > i with nums[j] > nums[i] (there's
guaranteed to be at least one, since the suffix is non-increasing and
starts above nums[i] isn't required — nums[i+1] alone already
satisfies nums[i+1] > nums[i]), and swap nums[i] and nums[j].
Finally, since the suffix after position i is still in
non-increasing order, reverse it to put it into the smallest possible
(ascending) order — this two-pointer reversal is what turns the
largest-possible suffix into the smallest-possible one, which is
exactly what "next" permutation requires: the minimal increase.
Generating and sorting all permutations to find the next one would cost O(n! log n!) time; this approach does it directly in a single pass plus a bounded reversal.
def next_lexicographical_sequence(nums: list[int]) -> None:
n = len(nums)
# Step 1: find the first index (from the right) where order breaks.
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]:
i -= 1
if i >= 0:
# Step 2: find the smallest value to the right of i that's
# still greater than nums[i], and swap them.
j = n - 1
while nums[j] <= nums[i]:
j -= 1
nums[i], nums[j] = nums[j], nums[i]
# Step 3: reverse the suffix after i (two-pointer in-place reversal)
# to put it in ascending order.
left, right = i + 1, n - 1
while left < right:
nums[left], nums[right] = nums[right], nums[left]
left += 1
right -= 1
# nums is modified in place; nothing to return
Complexity: O(n) time — the initial scan, the second scan, and the final reversal each touch each index at most a constant number of times. O(1) extra space, since everything happens in place.
Share this question