Practice › Sliding Window
Minimum Size Subarray Sum
Medium · Sliding Window · Asked at Amazon, Google, Goldman Sachs
All numbers are positive. Find the length of the shortest contiguous subarray whose sum is at least s. Print 0 if there is none.
Input
First line: n. Second line: n positive integers. Third line: s.
Output
The minimal length, or 0.
Constraints
- 1 ≤ n ≤ 10^5
- 1 ≤ a[i] ≤ 10^4
- 1 ≤ s ≤ 10^9
Example 1
Input
6 2 3 1 2 4 3 7
Output
2
Example 2
Input
3 1 1 1 10
Output
0
Hints
- All numbers are positive, so growing a window only increases its sum and shrinking only decreases it.
- Expand the right end; while the sum is ≥ s, record the length and shrink from the left.
Approach
A variable-size window. Move r forward, adding a[r]. While the window sum is at least s, the window qualifies: record r − l + 1, then remove a[l] and advance l to look for something shorter. Each index enters and leaves the window once. If no window ever qualifies, print 0.
Complexity: O(n) time · O(1) space
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
long long s;
cin >> s;
long long sum = 0;
int best = INT_MAX, l = 0;
for (int r = 0; r < n; r++) {
sum += a[r];
while (sum >= s) {
best = min(best, r - l + 1);
sum -= a[l++];
}
}
cout << (best == INT_MAX ? 0 : best) << "\n";
return 0;
}Python solution
import sys
data = list(map(int, sys.stdin.read().split()))
n = data[0]
a, s = data[1 : n + 1], data[n + 1]
best, total, l = n + 1, 0, 0
for r in range(n):
total += a[r]
while total >= s:
best = min(best, r - l + 1)
total -= a[l]
l += 1
print(0 if best == n + 1 else best)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
long s = sc.nextLong(), sum = 0;
int best = Integer.MAX_VALUE, l = 0;
for (int r = 0; r < n; r++) {
sum += a[r];
while (sum >= s) {
best = Math.min(best, r - l + 1);
sum -= a[l++];
}
}
System.out.println(best == Integer.MAX_VALUE ? 0 : best);
}
}Solve Minimum Size Subarray Sum online · All practice problems