Minimum Size Subarray Sum
- 1 min read
- Array
- LC-Medium
- Sliding Window
3 years ago
Solution
- IMPORTANT POINT - The solution only works because array contains positive numbers
- If there are negative numbers, the logic for shifting the sliding window wouldn't work, because it assumes that each number is positive, and that every time we reduce the sliding window, our sum will strictly decrease and not increase (due to presence of a negative number)
- Sliding window solution - Expand window until current sum is greater than or equal to target
- Decrease sliding window from left, while updating answer and decrementing current sum with number that just left our window
| Time | Space | Explanation |
|---|---|---|
O(n) | O(1) |
function minSubArrayLen(target: number, nums: number[]): number {
let l = 0;
let cur_sum = 0;
let min_len = Infinity;
for (let r = 0; r < nums.length; r++) {
cur_sum += nums[r];
while (cur_sum >= target) {
min_len = Math.min(min_len, r - l + 1)
cur_sum -= nums[l++];
}
}
return minlen === Infinity ? 0 : min_len;
};