Shortest run with sum at least K, negatives allowed
Hard · Target 35 minutes · Sliding window· Type asked at
Google
G-Research
J.P. Morgan
Given an integer array nums, which may contain negative numbers, and an integer
K ≥ 1, return the length of the shortest non-empty contiguous subarray whose sum is at least
K, or 0 if there is none.
Examples
| Input | Output | Why |
|---|---|---|
nums = [2,-1,2], K = 3 | 3 | Only the whole array reaches 3. |
nums = [1,2], K = 4 | 0 | |
nums = [84,-37,32,40,95], K = 167 | 3 | 32 + 40 + 95. |
Constraints
- 1 ≤ n ≤ 10⁵
- −10⁵ ≤ nums[i] ≤ 10⁵
- 1 ≤ K ≤ 10⁹
Hints
Hint 1
Why does the positive-number window fail? Find a small array where shrinking from the left makes the sum larger.
Hint 2
With prefix sums P, a subarray i..j−1 has sum P[j] − P[i]. You want j − i small with P[j] − P[i] ≥ K.
Hint 3
Keep candidate starts i in a deque with increasing P[i]. A later start with a smaller or equal prefix makes earlier ones useless; a start that has already succeeded can be retired.
Where people lose marks
- Running the positive-number window on this input: [2, −1, 2] with K = 3 already breaks it.
- Prefix sums in 32-bit integers: 10⁵ × 10⁵ overflows. Use 64 bits.
- Popping the front only once per step instead of while the condition holds.
Dry run on [2,-1,2],3
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 / 5nums20-1122P00211233
Prefix sums: P = [0, 2, 1, 3]. The subarray i..j−1 sums to P[j] − P[i]. Note that the plain window would drop the 2 at the front once it saw the sum 1 fall short, and miss the answer.
-
Step 2 / 5P00j211233best—
j = 0. Nothing reaches K yet. Candidate starts: [0].
-
Step 3 / 5P0021j1233best—
j = 1. Nothing reaches K yet. Candidate starts: [0, 1].
-
Step 4 / 5P002112j33best—
j = 2. P[2] = 1 is no larger than P at 1, so drop that start. Candidate starts: [0, 2].
-
Step 5 / 5P00211233jbest3
j = 3. P[3] − P[0] = 3 ≥ 3: length 3, retire start 0. Candidate starts: [2, 3].
How to think about it
With negative numbers, dropping an element from the left can make the sum go up, so "the sum is
at least K" no longer behaves predictably as the window moves, and the plain window gives wrong answers. Work
with prefix sums instead: P[0] = 0 and P[j] = nums[0] + … + nums[j − 1], so the
subarray from i to j − 1 sums to P[j] − P[i].
Scan j from left to right and keep a deque of candidate starts i, with increasing P[i]. Two
rules keep it small. First, while P[j] − P[front] ≥ K, record j − front and pop
the front: any later end would give a longer subarray from that start, so it is done. Second, before adding
j, pop from the back every start with P[back] ≥ P[j]: j is a later start with a smaller or equal
prefix, so it beats them for every future end. Each index enters and leaves once, so the scan is O(n).
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 shortest_at_least(nums, K):
P = [0]
for x in nums:
P.append(P[-1] + x) # P[j] - P[i] is the sum of nums[i:j]
starts = deque() # candidate starts, P increasing
best = 0
for j, p in enumerate(P):
while starts and p - P[starts[0]] >= K:
i = starts.popleft() # done: later ends are only longer
if best == 0 or j - i < best:
best = j - i
while starts and P[starts[-1]] >= p:
starts.pop() # j is a later, no-worse start
starts.append(j)
return best#include <vector>
#include <deque>
int solve(const std::vector<int>& nums, long long K) {
int n = (int)nums.size();
std::vector<long long> P(n + 1, 0);
for (int i = 0; i < n; ++i) P[i + 1] = P[i] + nums[i]; // 64-bit prefix sums
std::deque<int> starts; // candidate starts, P increasing
int best = 0;
for (int j = 0; j <= n; ++j) {
while (!starts.empty() && P[j] - P[starts.front()] >= K) {
int i = starts.front(); // done: later ends are only longer
starts.pop_front();
if (best == 0 || j - i < best) best = j - i;
}
while (!starts.empty() && P[starts.back()] >= P[j]) starts.pop_back();
starts.push_back(j);
}
return best;
}import java.util.*;
class Solution {
public int shortestAtLeast(int[] nums, long K) {
int n = nums.length;
long[] P = new long[n + 1];
for (int i = 0; i < n; i++) P[i + 1] = P[i] + nums[i]; // 64-bit prefix sums
Deque<Integer> starts = new ArrayDeque<>(); // candidate starts, P increasing
int best = 0;
for (int j = 0; j <= n; j++) {
while (!starts.isEmpty() && P[j] - P[starts.peekFirst()] >= K) {
int i = starts.pollFirst(); // done: later ends are only longer
if (best == 0 || j - i < best) best = j - i;
}
while (!starts.isEmpty() && P[starts.peekLast()] >= P[j]) starts.pollLast();
starts.addLast(j);
}
return best;
}
}function shortestAtLeast(nums, K) {
const P = [0];
for (const x of nums) P.push(P[P.length - 1] + x); // P[j] - P[i] = sum of nums[i..j-1]
const dq = []; // candidate starts, P increasing
let head = 0, best = 0;
for (let j = 0; j < P.length; j++) {
while (dq.length > head && P[j] - P[dq[head]] >= K) {
const i = dq[head++]; // done: later ends are only longer
if (best === 0 || j - i < best) best = j - i;
}
while (dq.length > head && P[dq[dq.length - 1]] >= P[j]) dq.pop(); // j is a no-worse start
dq.push(j);
}
return best;
}use std::collections::VecDeque;
fn solve(nums: &[i64], k: i64) -> usize {
let mut p = vec![0i64; nums.len() + 1];
for i in 0..nums.len() { p[i + 1] = p[i] + nums[i]; } // p[j] - p[i] = sum of nums[i..j]
let mut starts: VecDeque<usize> = VecDeque::new(); // candidate starts, p increasing
let mut best = 0usize;
for j in 0..p.len() {
while let Some(&i) = starts.front() {
if p[j] - p[i] < k { break; }
starts.pop_front(); // done: later ends are only longer
if best == 0 || j - i < best { best = j - i; }
}
while let Some(&i) = starts.back() {
if p[i] < p[j] { break; }
starts.pop_back(); // j is a later, no-worse start
}
starts.push_back(j);
}
best
}import qualified Data.Sequence as S
import Data.Sequence (Seq, ViewL(..), ViewR(..), viewl, viewr, (|>))
-- Prefix sums, then a deque (Data.Sequence) of candidate starts with increasing prefix.
solve :: [Int] -> Int -> Int
solve nums k = go (zip [0 ..] ps) S.empty 0
where
ps = scanl (+) 0 nums
go [] _ best = best
go ((j, p) : rest) dq best =
let (dq1, best1) = front dq best
front d b = case viewl d of
(i, q) :< d' | p - q >= k -> front d' (if b == 0 || j - i < b then j - i else b)
_ -> (d, b)
back d = case viewr d of
d' :> (_, q) | q >= p -> back d'
_ -> d
in go rest (back dq1 |> (j, p)) best1Variants to try
- All numbers positive: the plain window solves it with O(1) space; see the shortest-subarray problem earlier in the chapter.
- Longest subarray with sum at least K: a different deque argument, on starts with decreasing prefix from the left.
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 → Medium25 minLongest run whose spread is at most a limit
The validity test needs the window's maximum and minimum. Two monotone deques keep both as the window slides.
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 → Medium25 minLongest run whose spread is at most a limit
The validity test needs the window's maximum and minimum. Two monotone deques keep both as the window slides.
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.