Longest run whose spread is at most a limit
Medium · Target 25 minutes · Sliding window· Type asked at
Google
Barclays
Optiver
Given an array nums and a non-negative integer limit, return the length
of the longest contiguous subarray in which the largest and smallest elements differ by at most
limit.
Examples
| Input | Output | Why |
|---|---|---|
nums = [8,2,4,7], limit = 4 | 2 | [2,4] or [4,7]. |
nums = [10,1,2,4,7,2], limit = 5 | 4 | [2,4,7,2]. |
nums = [4,2,2,2,4,4,2,2], limit = 0 | 3 | Three equal values in a row. |
Constraints
- 1 ≤ n ≤ 10⁵
- 1 ≤ nums[i] ≤ 10⁹
- 0 ≤ limit ≤ 10⁹
Hints
Hint 1
If a run's spread is within the limit, so is every run inside it. So the variable window applies; the hard part is the test.
Hint 2
You need the maximum and minimum of the window after every step, including after removals from the left.
Hint 3
Keep a deque of indices with decreasing values for the maximum, and one with increasing values for the minimum. Pop from the front when an index leaves the window.
Where people lose marks
- Storing values instead of indices in the deques: then you cannot tell whether the front has left the window.
- Shrinking by one step with
if: one removal may not bring the spread within the limit. - Using a sorted multiset: it works, in O(n log n), and is a fine fallback if you forget the deque.
Dry run on [10,1,2,4,7,2],5
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 / 6nums100lo/hi1122437425max deque[10]min deque[10]best1
10 enters. Max 10, min 10, spread 0. Longest so far: 1.
-
Step 2 / 6nums10011lo/hi22437425max deque[1]min deque[1]best1
1 enters. Max 10, min 1, spread 9. Over 5, so move lo to 1; the spread is now 0.
-
Step 3 / 6nums10011lo22hi437425max deque[2]min deque[1, 2]best2
2 enters. Max 2, min 1, spread 1. Longest so far: 2.
-
Step 4 / 6nums10011lo2243hi7425max deque[4]min deque[1, 2, 4]best3
4 enters. Max 4, min 1, spread 3. Longest so far: 3.
-
Step 5 / 6nums1001122lo4374hi25max deque[7]min deque[2, 4, 7]best3
7 enters. Max 7, min 1, spread 6. Over 5, so move lo to 2; the spread is now 5.
-
Step 6 / 6nums1001122lo437425himax deque[7, 2]min deque[2]best4
2 enters. Max 7, min 2, spread 5. Longest so far: 4.
How to think about it
The spread of a run can only shrink when the run shrinks, so the longest valid window can be found by growing on the right and shrinking on the left. What a sum or a count does in the earlier problems, the maximum and minimum have to do here, and they are harder: when the maximum leaves the window, the next one is not obvious.
A monotone deque answers that. For the maximum, keep indices whose values strictly decrease from front to back. A new element first removes from the back every index with a value at most its own: those can never be the maximum again while the new element is in the window, because it is at least as large and leaves later. The front is then the maximum. When the window's left end passes the front index, pop it. The minimum uses the mirror deque. Each index enters and leaves each deque once, so the whole scan is linear.
Complexity. Time O(n) · Space O(n)
The solution, in six languages
Each one is compiled and run against the test table before it is published. Java is reviewed by hand.
from collections import deque
def longest_within_limit(nums, limit):
hi_q, lo_q = deque(), deque() # indices: values decreasing / increasing
best = lo = 0
for hi, x in enumerate(nums):
while hi_q and nums[hi_q[-1]] <= x:
hi_q.pop()
while lo_q and nums[lo_q[-1]] >= x:
lo_q.pop()
hi_q.append(hi)
lo_q.append(hi)
while nums[hi_q[0]] - nums[lo_q[0]] > limit: # spread too wide: shrink
lo += 1
if hi_q[0] < lo:
hi_q.popleft()
if lo_q[0] < lo:
lo_q.popleft()
best = max(best, hi - lo + 1)
return best#include <vector>
#include <deque>
#include <algorithm>
int solve(const std::vector<int>& nums, int limit) {
std::deque<int> mx, mn; // indices: values decreasing / increasing
int best = 0, lo = 0;
for (int hi = 0; hi < (int)nums.size(); ++hi) {
while (!mx.empty() && nums[mx.back()] <= nums[hi]) mx.pop_back();
while (!mn.empty() && nums[mn.back()] >= nums[hi]) mn.pop_back();
mx.push_back(hi);
mn.push_back(hi);
while (nums[mx.front()] - nums[mn.front()] > limit) { // spread too wide: shrink
++lo;
if (mx.front() < lo) mx.pop_front();
if (mn.front() < lo) mn.pop_front();
}
best = std::max(best, hi - lo + 1);
}
return best;
}import java.util.*;
class Solution {
public int longestWithinLimit(int[] nums, int limit) {
Deque<Integer> mx = new ArrayDeque<>(), mn = new ArrayDeque<>(); // indices
int best = 0, lo = 0;
for (int hi = 0; hi < nums.length; hi++) {
while (!mx.isEmpty() && nums[mx.peekLast()] <= nums[hi]) mx.pollLast();
while (!mn.isEmpty() && nums[mn.peekLast()] >= nums[hi]) mn.pollLast();
mx.addLast(hi);
mn.addLast(hi);
while (nums[mx.peekFirst()] - nums[mn.peekFirst()] > limit) { // too wide: shrink
lo++;
if (mx.peekFirst() < lo) mx.pollFirst();
if (mn.peekFirst() < lo) mn.pollFirst();
}
best = Math.max(best, hi - lo + 1);
}
return best;
}
}function longestWithinLimit(nums, limit) {
// Indices with decreasing (mx) and increasing (mn) values; head pointers instead of shift().
const mx = [], mn = [];
let mxH = 0, mnH = 0, best = 0, lo = 0;
for (let hi = 0; hi < nums.length; hi++) {
while (mx.length > mxH && nums[mx[mx.length - 1]] <= nums[hi]) mx.pop();
while (mn.length > mnH && nums[mn[mn.length - 1]] >= nums[hi]) mn.pop();
mx.push(hi); mn.push(hi);
while (nums[mx[mxH]] - nums[mn[mnH]] > limit) { // spread too wide: shrink
lo++;
if (mx[mxH] < lo) mxH++;
if (mn[mnH] < lo) mnH++;
}
best = Math.max(best, hi - lo + 1);
}
return best;
}use std::collections::VecDeque;
fn solve(nums: &[i64], limit: i64) -> usize {
let (mut mx, mut mn) = (VecDeque::new(), VecDeque::new()); // indices: decreasing / increasing
let (mut best, mut lo) = (0usize, 0usize);
for hi in 0..nums.len() {
while mx.back().map_or(false, |&i: &usize| nums[i] <= nums[hi]) { mx.pop_back(); }
while mn.back().map_or(false, |&i: &usize| nums[i] >= nums[hi]) { mn.pop_back(); }
mx.push_back(hi);
mn.push_back(hi);
while nums[mx[0]] - nums[mn[0]] > limit { // spread too wide: shrink
lo += 1;
if mx[0] < lo { mx.pop_front(); }
if mn[0] < lo { mn.pop_front(); }
}
best = best.max(hi + 1 - lo);
}
best
}import qualified Data.Map.Strict as M
import Data.Array
-- A multiset (value -> count) gives the window's minimum and maximum in O(log n): the
-- functional stand-in for the two deques, with the same window logic.
solve :: [Int] -> Int -> Int
solve nums limit = third (foldl step (M.empty, 0, 0) (zip [0 ..] nums))
where
arr = listArray (0, length nums - 1) nums
third (_, _, b) = b
spread m = fst (M.findMax m) - fst (M.findMin m)
remove x = M.update (\c -> if c == 1 then Nothing else Just (c - 1)) x
step (m, lo, best) (hi, x) =
let (m', lo') = shrink (M.insertWith (+) x 1 m) lo
in (m', lo', max best (hi - lo' + 1))
shrink m lo
| spread m > limit = shrink (remove (arr ! lo) m) (lo + 1)
| otherwise = (m, lo)Variants to try
- The maximum of every window of fixed size k is the same deque without the second test: see the first problem of this module.
- Count the runs within the limit: add hi − lo + 1 at each step.
Next problems
Maximum of every window
A deque of candidates, kept in falling order, gives the maximum of every window in one pass.
Open the problem → Hard35 minShortest run with sum at least K, negatives allowed
Negative numbers break the plain window. Prefix sums turn the question into pairs of indices, and a deque keeps only the starts that can still win.
Open the problem → Easy10 minBest total over k consecutive days
A window of fixed width slides one place at a time: add the element that enters, subtract the one that leaves.
Open the problem →Write a solution and run it against the real test table.
Keep going
Maximum of every window
A deque of candidates, kept in falling order, gives the maximum of every window in one pass.
Open the problem → Hard35 minShortest run with sum at least K, negatives allowed
Negative numbers break the plain window. Prefix sums turn the question into pairs of indices, and a deque keeps only the starts that can still win.
Open the problem → Easy10 minBest total over k consecutive days
A window of fixed width slides one place at a time: add the element that enters, subtract the one that leaves.
Open the problem → Sliding windowThe pattern behind it
A window that grows on the right, shrinks on the left, and holds an invariant at all times.
Read the pattern →Preparing for a real process? Quant interview preparation, or book a free 20-minute call.