The shortest part to sort so the whole array is sorted
Medium · Target 15 minutes · Two pointers· Type asked at
Deutsche Bank
Nvidia
XTX Markets
You're given an integer array nums. Find the shortest continuous subarray that, if you sorted
just that part in ascending order, would leave the whole array sorted, and return its length. If the array's
sorted already the answer's 0.
Examples
| Input | Output | Why |
|---|---|---|
nums = [2, 6, 4, 8, 10, 9, 15] | 5 | You'd sort 6, 4, 8, 10, 9 and I think you'll find everything else is already where it should be. |
nums = [1, 2, 3, 4] | 0 | |
nums = [1, 3, 2, 2, 2] | 4 | The 3 has to end up behind all three 2's, so the part to sort runs from the 3 to the end. |
Constraints
- 1 ≤ n ≤ 10⁴
- −10⁵ ≤ nums[i] ≤ 10⁵
Hints
Hint 1
Sorting a copy and comparing the two works in O(n log n), but do you think you could say where the part to sort has to end without sorting anything at all?
Hint 2
I'd walk left to right and keep the biggest value you've seen so far. Any element that's smaller than that maximum is out of place, which means the part you sort has to reach at least that far.
Hint 3
The last element like that is your right end. If you do the same thing from the right with the running minimum, the last element that's bigger than it gives you the left end.
Where people lose marks
- Taking the first place where nums[i] > nums[i + 1] as the left end. In 1, 3, 5, 4, 2 the first drop is at the 5, but the 2 at the end has to go in front of the 3, so the part to sort starts at the 3.
- Comparing with ≤ in place of <, when an equal value next to the maximum is probably fine where it is and counting it would stretch the answer for no reason.
- Forgetting about the array that's sorted already. If neither pass finds anything the answer's 0, and it's quite easy to get that wrong by working out right − left + 1 anyway.
Dry run on [2,6,4,8,10,9,15]
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 / 3nums2061428310495right156right5
Left to right with the running maximum, the last value smaller than the maximum before it is at index 5 (9 after a 10). That's the right end.
-
Step 2 / 3nums2061left428310495right156left1right5
Right to left with the running minimum, the last value bigger than the minimum after it is 6 at index 1, so that's where the part to sort starts.
-
Step 3 / 3nums2061428310495156length5
Sorting positions 1 to 5 is enough, which is 5 values.
How to think about it
The easy answer is to sort a copy and find the first and last places where it differs from the original, which is O(n log n). You can get it down to O(n) with a pass from each end.
Going left to right I keep the biggest value I've seen so far. If nums[i] is smaller than that, it's
sitting after something bigger than it, so it has to move and the part you sort must reach at least as far as
i. The last i where that happens is the right end. If nothing after it is smaller than
the maximum so far, everything after it is already in place.
The left end comes from the mirror image. Going right to left you keep the smallest value you've seen, and
the last index (counting from the right) where nums[i] is bigger than that minimum is where the part
to sort starts. If the first pass never found anything the array's sorted and the answer's 0.
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 find_unsorted_subarray(nums):
n = len(nums)
hi, right = float('-inf'), -1
for i in range(n): # anything below the running max must move
if nums[i] < hi:
right = i
else:
hi = nums[i]
lo, left = float('inf'), n
for i in range(n - 1, -1, -1): # anything above the running min must move
if nums[i] > lo:
left = i
else:
lo = nums[i]
return 0 if right < 0 else right - left + 1#include <vector>
#include <climits>
int solve(const std::vector<int>& nums) {
int n = (int)nums.size(), hi = INT_MIN, right = -1, lo = INT_MAX, left = n;
for (int i = 0; i < n; ++i) // anything below the running max must move
if (nums[i] < hi) right = i; else hi = nums[i];
for (int i = n - 1; i >= 0; --i) // anything above the running min must move
if (nums[i] > lo) left = i; else lo = nums[i];
return right < 0 ? 0 : right - left + 1;
}class Solution {
public int findUnsortedSubarray(int[] nums) {
int n = nums.length, hi = Integer.MIN_VALUE, right = -1, lo = Integer.MAX_VALUE, left = n;
for (int i = 0; i < n; i++) // anything below the running max must move
if (nums[i] < hi) right = i; else hi = nums[i];
for (int i = n - 1; i >= 0; i--) // anything above the running min must move
if (nums[i] > lo) left = i; else lo = nums[i];
return right < 0 ? 0 : right - left + 1;
}
}function findUnsortedSubarray(nums) {
const n = nums.length;
let hi = -Infinity, right = -1, lo = Infinity, left = n;
for (let i = 0; i < n; i++) { // anything below the running max must move
if (nums[i] < hi) right = i; else hi = nums[i];
}
for (let i = n - 1; i >= 0; i--) { // anything above the running min must move
if (nums[i] > lo) left = i; else lo = nums[i];
}
return right < 0 ? 0 : right - left + 1;
}fn solve(nums: &[i64]) -> i64 {
let n = nums.len() as i64;
let (mut hi, mut right) = (i64::MIN, -1i64);
for (i, &x) in nums.iter().enumerate() { // anything below the running max must move
if x < hi { right = i as i64; } else { hi = x; }
}
let (mut lo, mut left) = (i64::MAX, n);
for (i, &x) in nums.iter().enumerate().rev() { // anything above the running min must move
if x > lo { left = i as i64; } else { lo = x; }
}
if right < 0 { 0 } else { right - left + 1 }
}solve :: [Int] -> Int
solve nums
| null bad = 0
| otherwise = right - left + 1
where
n = length nums
-- anything below the running max must move
runMax = scanl1 max nums
bad = [i | (i, x, m) <- zip3 [0 ..] nums (minBound : runMax), x < m]
right = last bad
-- anything above the running min (from the right) must move
runMin = tail (scanr min maxBound nums)
left = head [i | (i, x, m) <- zip3 [0 ..] nums runMin, x > m]Variants to try
- If you're asked for the subarray itself as well as its length, I'd just return the two ends the passes found, since you've already got them.
- If you're allowed to reverse a part in place of sorting it, it's a different question: find the bad part the same way and then check that reversing it gives a sorted array.
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.