Learn
Practice
Interview
Resources
Newsletter
F
Toggle theme
0
F
0
Toggle menu
Animations
← Back to All Animations
Shortest Subarray with Sum at Least K
Bookmark
Brute Force
Prefix Sum + Deque
Input
Standard
Example 2
Negative
Custom
nums
=
[2, -1, 2]
,
k
=
3
minLen =
∞
nums
2
-1
2
0
1
2
try every subarray; keep the shortest with sum ≥ 3
minLen =
∞
nums
2
-1
2
0
1
2
try every subarray; keep the shortest with sum ≥ 3
minLen =
∞
i
nums
2
-1
2
0
1
2
j
sum[0..0] =
0
<
3
new window at i =
0
minLen =
∞
i
nums
2
-1
2
0
1
2
j
sum[0..1] =
1
<
3
sum 1 < 3 → extend j to
2
minLen =
3
i
nums
2
-1
2
0
1
2
j
sum[0..2] =
3
≥
3
valid length
3
new min
minLen =
3
i
nums
2
-1
2
0
1
2
j
sum[1..1] =
0
<
3
new window at i =
1
minLen =
3
i
nums
2
-1
2
0
1
2
j
sum[1..2] =
1
<
3
sum 1 < 3 → extend j to
2
minLen =
3
nums
2
-1
2
0
1
2
no window from i = 1
reaches 3
minLen =
3
i
nums
2
-1
2
0
1
2
j
sum[2..2] =
0
<
3
new window at i =
2
minLen =
3
nums
2
-1
2
0
1
2
no window from i = 2
reaches 3
minLen =
3
nums
2
-1
2
0
1
2
shortest length =
3
algo
master
.
io
Step:
Try every subarray; keep the shortest whose sum ≥ 3.
0 / 12
Input
Standard
Example 2
Negative
Custom
nums
=
[2, -1, 2]
,
k
=
3
0 / 12
algo
master
.
io
Step:
Try every subarray; keep the shortest whose sum ≥ 3.
