Minimum Window Sum — Problem Statement & Solution Guide
Problem Description
Given an array of integers arr and a target integer target, find the length of the shortest continuous subarray where the total sum is at least target. If no such subarray exists, return 0.
Examples
Input
[2,3,1,2,4,3], 7
Output
2
Explanation: Step-by-step: with input [2,3,1,2,4,3] and target 7, we start by expanding the window from the left. We add elements to the window until the sum is at least 7. The first such window is [4,3] with a sum of 7. We then try to minimize the window by moving the left pointer to the right. The minimum window is [4,3] with a length of 2.
Input
[1,4,4], 4
Output
1
Explanation: Step-by-step: with input [1,4,4] and target 4, we start by expanding the window from the left. We add elements to the window until the sum is at least 4. The first such window is [4] with a sum of 4. This is already the minimum window with a length of 1.
Constraints
- 1 <= n <= 10^5
- 1 <= arr[i] <= 10^4
- 1 <= target <= 10^9
Optimal Approach & Strategy
Two pointers for a sliding window. Expand right pointer adding to sum. While sum >= target, update minLength and shrink window by moving left pointer. Time O(N), Space O(1).
Brute Force Approach
Check all possible subarrays. Time O(N^2).
Verified Code Solutions
function minSubArrayLen(target, nums) { let left = 0, currSum = 0, minLen = Infinity; for (let right = 0; right < nums.length; right++) { currSum += nums[right]; while (currSum >= target) { minLen = Math.min(minLen, right - left + 1); currSum -= nums[left]; left++; } } return minLen === Infinity ? 0 : minLen; }class Solution { public: int minSubArrayLen(int target, vector<int>& nums) { int left = 0, currSum = 0, minLen = INT_MAX; for (int right = 0; right < nums.size(); right++) { currSum += nums[right]; while (currSum >= target) { minLen = min(minLen, right - left + 1); currSum -= nums[left]; left++; } } return minLen == INT_MAX ? 0 : minLen; } };class Solution { public int minSubArrayLen(int target, int[] nums) { int left = 0, currSum = 0, minLen = Integer.MAX_VALUE; for (int right = 0; right < nums.length; right++) { currSum += nums[right]; while (currSum >= target) { minLen = Math.min(minLen, right - left + 1); currSum -= nums[left]; left++; } } return minLen == Integer.MAX_VALUE ? 0 : minLen; } }def minSubArrayLen(target, nums): left, curr_sum, min_len = 0, 0, float('inf'); for right in range(len(nums)): curr_sum += nums[right]; while curr_sum >= target: min_len = min(min_len, right - left + 1); curr_sum -= nums[left]; left += 1; return 0 if min_len == float('inf') else min_lenfunction minSubArrayLen(target, nums) { let left = 0, currSum = 0, minLen = Infinity; for (let right = 0; right < nums.length; right++) { currSum += nums[right]; while (currSum >= target) { minLen = Math.min(minLen, right - left + 1); currSum -= nums[left]; 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.