183. Next Arrangement
A combination lock shows a row of digit wheels, and the array nums holds the digit currently showing on each wheel. The lock owner wants to step through every arrangement of those same digits in dictionary order, comparing arrangements as sequences from left to right.
Rearrange nums in place into the arrangement that comes immediately after the current one in that order, that is, the smallest arrangement of the same digits that is strictly greater than the current one. If the current arrangement is already the greatest possible, wrap around and rearrange nums into the smallest one, which is ascending order. Repeated digits are allowed. The function returns nothing; the array itself is checked.
Example 1
- Input:
- nums = [1,2,3]
- Output:
- [1,3,2]
- Explanation:
The arrangements of 1, 2, 3 in order are 123, 132, 213, ... so after 123 comes 132.
Example 2
- Input:
- nums = [3,2,1]
- Output:
- [1,2,3]
- Explanation:
321 is the greatest arrangement, so it wraps around to the smallest, 123.
Example 3
- Input:
- nums = [1,1,5]
- Output:
- [1,5,1]
- Explanation:
With a repeated digit, the arrangements are 115, 151 and 511, so 115 is followed by 151.
Constraints
1 ≤ nums.length ≤ 2000
0 ≤ nums[i] ≤ 9
How this problem is judged
- Answers
- Your answer must match exactly. Numbers compare by value, so 2 and 2.0 are equal.
- Graded
- Your answer is read from
numsafter your method returns. - Time per case
- Python 1,200 msC++ 300 msJava 600 msJavaScript 600 msTypeScript 600 ms
Expected complexity
- Time
- O(n)
- Space
- O(1)