Shortest Subarray Above a Threshold
National Olympiad — National round (2022 season)
Submission name: subsum.cpp
Problem summary
Find the shortest contiguous nonempty subarray whose sum is strictly greater than W. If none exists, output 0.
Input
N W, followed by N positive integers.
Output
The minimum qualifying length, or 0.
Constraints
1 < N < 5,000,000; 0 < W < 100,000; 0 < values < 10,000.
Worked example
An independently prepared example for this explanation.
Input
4 4 1 2 1 3
Output
3
Solution analysis
- Positive values make a sliding window possible. Extend the window with each incoming value. While its sum is greater than W, record its length and remove its leftmost value.
- Each removal tries a shorter window with the same right endpoint. Once the sum is at most W, further removals cannot help at that endpoint. A deque lets the program stream input without storing the entire sequence.
- For 1,2,1,3 and W=4, the first three values sum to 4 and do not qualify. At the final value, length 4 qualifies; removing the first value leaves 2,1,3 with sum 6 and length 3. Removing 2 leaves sum 4, so the answer is 3.
Why it works
For each right endpoint, shrinking examines all still-useful qualifying starts until positivity makes every shorter window fail. A start removed earlier already gave a qualifying window with an earlier endpoint, so using it later could only be longer. Thus no optimal length is missed. Every value enters and leaves the deque at most once.
Watch out. The comparison is strictly greater, not greater than or equal. The method depends on all values being positive. Report 0 when no update occurs.
Commented C++17 solution
An independently written complete program with standard headers.
#include <iostream>
#include <deque>
#include <algorithm>
using namespace std;
int main() {
ios::sync_with_stdio(false);
cin.tie(nullptr);
int n, threshold;
cin >> n >> threshold;
deque<int> window;
long long sum = 0;
int answer = n + 1;
for (int i = 0; i < n; i++) {
int value;
cin >> value;
window.push_back(value);
sum += value;
// Positive entries allow shrinking until this window stops qualifying.
while (sum > threshold) {
answer = min(answer, static_cast<int>(window.size()));
sum -= window.front();
window.pop_front();
}
}
if (answer == n + 1) {
answer = 0;
}
cout << answer << '\n';
}