The next permutation, in place
Medium · Target 20 minutes · Two pointers· Type asked at
IMC
Apple
Morgan Stanley
You're given an array of integers nums. Rearrange it into the next permutation in
lexicographic order, the smallest arrangement of the same values that's bigger than the one you've got, and
return it. If it's already the biggest arrangement there is, wrap round to the smallest one, which is the values
sorted ascending. You should use O(1) extra space.
Examples
| Input | Output | Why |
|---|---|---|
nums = [1, 2, 3] | [1, 3, 2] | |
nums = [3, 2, 1] | [1, 2, 3] | 3, 2, 1 is the biggest arrangement there is, so it wraps round to the smallest one. |
nums = [1, 1, 5] | [1, 5, 1] | With repeated values you still want the next distinct arrangement, and swapping the two 1's wouldn't change anything. |
nums = [2, 4, 3, 1] | [3, 1, 2, 4] |
Constraints
- 1 ≤ n ≤ 100
- 0 ≤ nums[i] ≤ 100
Hints
Hint 1
I'd look at the array from the right first and ask how long the run at the end is that only goes down, and why you can't make that bit any bigger by itself.
Hint 2
A run that only goes down is already in its biggest arrangement, so the change has to happen at i, the last index where nums[i] < nums[i + 1]. What do you think should go there?
Hint 3
You want the smallest value to the right of i that's still bigger than nums[i]. Once you've swapped it in the run after i is still going down, and you'd reverse it with two pointers to make it as small as it can be.
Where people lose marks
- Using nums[i] ≤ nums[i + 1] to find the pivot. With repeated values it'll stop on a level step, and swapping equal values just gives you the same array back.
- Sorting the suffix when reversing it is enough. It's already in descending order after the swap, so a sort costs O(n log n) for nothing.
- Forgetting the wrap-round. When there's no pivot the answer's the values in ascending order, and that's the whole array reversed.
Dry run on [2,4,3,1]
Read it one frame at a time, the way you would trace the code on paper in an interview. Each frame shows the state after the step it describes.
-
Step 1 / 5nums20i413213i0
Reading from the right, 4, 3, 1 only goes down, and the last step up is at index 0, where 2 < 4.
-
Step 2 / 5nums20i4132j13i0j2
Scanning back from the end, the first value you meet that's bigger than 2 is the 3 at index 2. Since the run goes down that's also the smallest one that's bigger, so you swap those two.
-
Step 3 / 5nums3041lo2213hilo1hi3
What's after index 0 is still going down after the swap, and you want it as small as possible, so lo and hi start at its two ends to reverse it.
-
Step 4 / 5nums3011lo2243hilo1hi3
lo is at 1 and hi is at 3, so those two trade places and both pointers move in by one.
-
Step 5 / 5nums30112243
They've met in the middle, and what you're left with, 3, 1, 2, 4, is the next permutation.
How to think about it
I'd start by reading the array from the right. At the end there's a run that only goes down (or stays
level), and a run like that is already in its biggest arrangement, so there's nothing you can do inside it to make
the whole array bigger. The first change has to be at i, the last index where
nums[i] < nums[i + 1]. If there isn't one the whole array is going down, and you wrap round by
reversing all of it.
At i you want the smallest value that's still bigger than nums[i], and it has to come from
the run to the right. Since that run's going down, it's the rightmost value bigger than nums[i], which a
scan from the end finds. Swap the two. The run after i is still going down after the swap, and the
smallest thing you can do with it is put it in ascending order, which here just means reversing it. That's the two
pointer part, with lo at i + 1 and hi at the end swapping towards each other.
Everything's one pass or less, so it's O(n) and it all happens in place.
Complexity. Time O(n) · Space O(1)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
def next_permutation(nums):
n = len(nums)
i = n - 2
while i >= 0 and nums[i] >= nums[i + 1]: # the run at the end that only goes down
i -= 1
if i >= 0:
j = n - 1
while nums[j] <= nums[i]: # the smallest value bigger than nums[i]
j -= 1
nums[i], nums[j] = nums[j], nums[i]
lo, hi = i + 1, n - 1
while lo < hi: # reverse the run with two pointers
nums[lo], nums[hi] = nums[hi], nums[lo]
lo += 1
hi -= 1
return nums#include <vector>
#include <utility>
std::vector<int> solve(std::vector<int> nums) {
int n = (int)nums.size(), i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) --i; // the run at the end that only goes down
if (i >= 0) {
int j = n - 1;
while (nums[j] <= nums[i]) --j; // the smallest value bigger than nums[i]
std::swap(nums[i], nums[j]);
}
for (int lo = i + 1, hi = n - 1; lo < hi; ++lo, --hi) // reverse the run with two pointers
std::swap(nums[lo], nums[hi]);
return nums;
}class Solution {
public int[] nextPermutation(int[] nums) {
int n = nums.length, i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--; // the run at the end that only goes down
if (i >= 0) {
int j = n - 1;
while (nums[j] <= nums[i]) j--; // the smallest value bigger than nums[i]
int t = nums[i]; nums[i] = nums[j]; nums[j] = t;
}
for (int lo = i + 1, hi = n - 1; lo < hi; lo++, hi--) { // reverse the run with two pointers
int t = nums[lo]; nums[lo] = nums[hi]; nums[hi] = t;
}
return nums;
}
}function nextPermutation(nums) {
const n = nums.length;
let i = n - 2;
while (i >= 0 && nums[i] >= nums[i + 1]) i--; // the run at the end that only goes down
if (i >= 0) {
let j = n - 1;
while (nums[j] <= nums[i]) j--; // the smallest value bigger than nums[i]
[nums[i], nums[j]] = [nums[j], nums[i]];
}
for (let lo = i + 1, hi = n - 1; lo < hi; lo++, hi--) // reverse the run with two pointers
[nums[lo], nums[hi]] = [nums[hi], nums[lo]];
return nums;
}fn solve(input: &[i64]) -> Vec<i64> {
let mut nums = input.to_vec();
let n = nums.len() as i64;
let mut i = n - 2;
while i >= 0 && nums[i as usize] >= nums[i as usize + 1] { i -= 1; } // the run at the end that only goes down
if i >= 0 {
let mut j = n - 1;
while nums[j as usize] <= nums[i as usize] { j -= 1; } // the smallest value bigger than nums[i]
nums.swap(i as usize, j as usize);
}
let (mut lo, mut hi) = (i + 1, n - 1);
while lo < hi { // reverse the run with two pointers
nums.swap(lo as usize, hi as usize);
lo += 1; hi -= 1;
}
nums
}-- Lists in place of an array: split off the run at the end that only goes down, then rebuild.
solve :: [Int] -> [Int]
solve nums = case pivot of
Nothing -> reverse nums -- the biggest arrangement wraps round
Just i ->
let (front, x : run) = splitAt i nums
-- run goes down, so the rightmost value bigger than x is the smallest such value
(bigger, rest) = span (> x) run
y = last bigger
run' = init bigger ++ [x] ++ rest -- still going down after the swap
in front ++ [y] ++ reverse run'
where
n = length nums
pivot = case [i | i <- [n - 2, n - 3 .. 0], nums !! i < nums !! (i + 1)] of
(i : _) -> Just i
[] -> NothingVariants to try
- If you're asked for the previous permutation it's the mirror image, where you find the last i with nums[i] > nums[i + 1] and swap in the largest smaller value from the right before you reverse what's after it.
- If you're asked for the k-th permutation of 1..n you don't have to take k steps, because the factorial number system lets you pick each position directly and that's O(n²).
Next problems
Pair with a given sum in a sorted array
The cleanest example of the two-pointer idea: sorted input, one pass, no extra memory.
Open the problem → Easy12 minCount the pairs whose sum is below a target
Sort it and start at both ends, and whenever the sum's small enough you'll have found a whole run of pairs in one go.
Open the problem → Easy10 minA palindrome, ignoring punctuation and case
Compare from both ends inward, stepping over anything that is not a letter or a digit. No cleaned copy of the string is needed.
Open the problem →Write a solution and run it against the real test table.
Keep going
Pair with a given sum in a sorted array
The cleanest example of the two-pointer idea: sorted input, one pass, no extra memory.
Open the problem → Easy12 minCount the pairs whose sum is below a target
Sort it and start at both ends, and whenever the sum's small enough you'll have found a whole run of pairs in one go.
Open the problem → Easy10 minA palindrome, ignoring punctuation and case
Compare from both ends inward, stepping over anything that is not a letter or a digit. No cleaned copy of the string is needed.
Open the problem → Two pointersThe pattern behind it
Two indices walking a sorted or paired structure, each step ruling out one candidate for good.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.