Two Pointers Rearranging in place
162. Next Permutation
You are given an array of integers nums. Rearrange its values into the next arrangement in dictionary
order.
Two arrangements of the same values compare the way words compare in a dictionary. Find the first position
where they differ: the arrangement with the smaller value there comes first. So [1, 3, 2] comes before
[2, 1, 3], because 1 is smaller than 2. The next arrangement is the one that comes right after nums
in this order. Two arrangements that hold the same value at every position are the same arrangement, even
if they swap two equal values. If no arrangement comes after nums, the next one wraps around to the first
arrangement: the values in ascending order.
Change nums itself and return nothing. Use only O(1) extra memory.
Example 1
Input: nums = [3, 6, 2, 9, 7, 5, 1]
[3,6,5,1,2,7,9]Explanation: The last four values, 9, 7, 5, 1, already fall from left to right, so no reordering of them alone makes the array larger. The 2 before them becomes 5, the smallest later value above 2, and the values left over, 1, 2, 7, 9, follow in ascending order.
Example 2
Input: nums = [-2, 7, -2, 7]
[-2,7,7,-2]Explanation: The values −2, −2, 7, 7 have six different arrangements. This one is the second in dictionary order, and the third one only swaps its last two values.
Example 3
Input: nums = [6, 6, -3, -8]
[-8,-3,6,6]Explanation: The values fall from left to right, so this is the last arrangement and nothing comes after it. The answer wraps around to the first arrangement, the values in ascending order.
Check your understanding
Work out the answer for this input before you write any code.
Constraints
1 ≤ nums.length ≤ 105-109 ≤ nums[i] ≤ 109
Clarifying questions
What you would ask an interviewer before writing any code.