Subarray with Given Sum — Problem Statement & Solution Guide
Problem Description
Given an array of integers representing bandwidth usage per second, find the shortest continuous time window where the total bandwidth is at least the given target. Return 0 if impossible.
DSA Pattern Breakdown
DSA Pattern Breakdown
"Subarray with Given Sum"
WHY DOES IT MATTER?
The Sliding Window pattern is essential for solving problems involving contiguous subarrays or substrings where the property of interest (like sum, count, or uniqueness) changes monotonically with window size. It is a cornerstone technique for optimizing brute-force O(n^2) solutions to O(n) by leveraging the fact that we don't need to recompute the state of the window from scratch when shifting the boundary.
OPTIMIZATION CHALLENGE
The key insight is that once the window sum exceeds the target, any further expansion of the window to the right will only increase the sum, making the window larger. Therefore, the optimal strategy is to immediately shrink the window from the left to see if a smaller valid window exists. This greedy shrinking ensures that we explore all potential minimal windows without redundant calculations.
REAL-WORLD CONNECTION
This pattern is analogous to monitoring network bandwidth or server load over time. Imagine you have a stream of data points representing bandwidth usage per second. You need to find the shortest time interval where the total data transferred exceeds a certain threshold to trigger an alert or scale up resources. The sliding window efficiently tracks this cumulative usage without storing the entire history, making it ideal for real-time streaming systems.
During the interview, explicitly state the assumption that the array contains only positive integers. This justifies the use of the sliding window technique. If the interviewer introduces negative numbers, pivot to discussing the Deque-based approach for prefix sums, demonstrating your depth of knowledge and ability to adapt to varying constraints.
COMPLEXITY AT A GLANCE
O(n)O(1)Core Theory — Why This Approach?
The problem of finding the shortest subarray with a sum at least equal to a target is a classic application of the Sliding Window technique, specifically optimized for arrays containing only positive integers. The core theoretical underpinning relies on the monotonicity of the prefix sum. As we extend the right boundary of the window, the sum strictly increases. Conversely, as we shrink the left boundary, the sum strictly decreases. This property allows us to use two pointers, left and right, to maintain a valid window where the sum is >= target. If the sum exceeds the target, we can safely move the left pointer inward to reduce the window size, thereby potentially finding a shorter valid window. This greedy shrinking ensures that for every right position, we find the smallest possible left that satisfies the condition, leading to an optimal solution.
Interview Questions on This Problem
Q1How would you modify this solution if the array could contain negative numbers?
If the array contains negative numbers, the sliding window approach fails because the sum is no longer monotonic with respect to window size. In this case, the problem transforms into finding the shortest subarray with a sum >= K, which can be solved in O(n) time using a Deque (Double-Ended Queue) to maintain a monotonic queue of prefix sums. Alternatively, a O(n log n) solution using a Binary Indexed Tree (Fenwick Tree) or Segment Tree can be employed to handle the non-monotonic nature of the sums.
Q2What is the time complexity of the sliding window approach, and why is it linear?
The time complexity is O(n). Although there are two nested loops in the implementation, the left pointer only moves forward and never resets. Across the entire execution, both left and right pointers traverse the array at most once. Therefore, the total number of operations is proportional to the length of the array, resulting in linear time complexity.
Q3How would you handle the case where the target sum is 0 or negative?
If the target sum is 0 or negative, and the array contains non-negative integers, the shortest subarray would be of length 0 (if empty subarrays are allowed) or 1 (if the minimum element is >= 0). However, typically in such problems, the target is positive. If the target is 0, the answer is 0 if we consider an empty window, or 1 if we must pick at least one element and the smallest element is >= 0. The standard sliding window logic assumes a positive target and positive array elements.
Examples
Input
[6, 5, 4, 3, 2, 1], 8
Output
2
Explanation: Step-by-step: Given the array [6, 5, 4, 3, 2, 1] and target 8, we start a sliding window from the beginning of the array. The initial window is [6]. The sum of this window is 6, which is less than the target. We expand the window by adding the next element, 5. The new window is [6, 5]. The sum of this window is 11, which is greater than the target. However, we need to find the shortest window, so we continue expanding the window. The next element is 4, and the new window is [6, 5, 4]. The sum of this window is 15, which is greater than the target. We can stop here because the window [6, 5, 4] is the shortest window that meets the condition.
Input
[3, 4, 5, 6, 7, 8], 12
Output
5
Explanation: Step-by-step: Given the array [3, 4, 5, 6, 7, 8] and target 12, we start a sliding window from the beginning of the array. The initial window is [3]. The sum of this window is 3, which is less than the target. We expand the window by adding the next element, 4. The new window is [3, 4]. The sum of this window is 7, which is less than the target. We continue expanding the window. The next element is 5, and the new window is [3, 4, 5]. The sum of this window is 12, which is equal to the target. We can stop here because the window [3, 4, 5] is the shortest window that meets the condition.
Constraints
- 1 <= n <= 10^5
- 1 <= arr[i] <= 10^4
- 1 <= target <= 10^9
Optimal Approach & Strategy
The optimized approach uses a sliding window with two pointers to maintain a running sum. By expanding the right pointer and shrinking the left pointer only when the sum exceeds the target, we ensure that each element is processed at most twice, reducing the time complexity to O(n).
Brute Force Approach
The brute force approach involves iterating over all possible starting indices and, for each start, iterating over all ending indices to calculate the sum of the subarray. This results in a time complexity of O(n^2) due to the nested loops, which is inefficient for large arrays.
Verified Code Solutions
function minSubArrayLen(target, nums) {
let left = 0, sum = 0, minLen = Infinity;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
minLen = Math.min(minLen, right - left + 1);
sum -= nums[left++];
}
}
return minLen === Infinity ? 0 : minLen;
}#include <vector>
#include <climits>
using namespace std;
int minSubArrayLen(int target, vector<int>& nums) {
int n = nums.size();
int minLen = INT_MAX;
int left = 0, sum = 0;
for (int right = 0; right < n; ++right) {
sum += nums[right];
while (sum >= target) {
minLen = min(minLen, right - left + 1);
sum -= nums[left++];
}
}
return minLen == INT_MAX ? 0 : minLen;
}public class Solution {
public int minSubArrayLen(int target, int[] nums) {
int n = nums.length;
int minLen = Integer.MAX_VALUE;
int left = 0, sum = 0;
for (int right = 0; right < n; right++) {
sum += nums[right];
while (sum >= target) {
minLen = Math.min(minLen, right - left + 1);
sum -= nums[left++];
}
}
return minLen == Integer.MAX_VALUE ? 0 : minLen;
}
}def min_subarray_len(target, nums):
left = 0
sum_ = 0
min_len = float('inf')
for right, val in enumerate(nums):
sum_ += val
while sum_ >= target:
min_len = min(min_len, right - left + 1)
sum_ -= nums[left]
left += 1
return 0 if min_len == float('inf') else min_lenfunction minSubArrayLen(target, nums) {
let left = 0, sum = 0, minLen = Infinity;
for (let right = 0; right < nums.length; right++) {
sum += nums[right];
while (sum >= target) {
minLen = Math.min(minLen, right - left + 1);
sum -= nums[left++];
}
}
return minLen === Infinity ? 0 : minLen;
}Asked in Top Tech Interviews
Solve in Interative Editor
Ready to test your code? Open our built-in compiler, run custom test suites, and see detailed complexity analysis reports instantly.