mediumSliding WindowPattern: Sliding Window
Minimum Window Sum Solution
Problem Statement
Given an array of integers `nums` and an integer `targetSum`, find the minimum length of a contiguous subarray whose sum is greater than or equal to `targetSum`. If no such subarray exists, return 0.
Examples
Example 1:
Input:{"nums":[2,3,1,2,4,3],"targetSum":7}
Output:2
Explanation: The contiguous subarray [4, 3] has the minimal length of 2 and its sum (7) is greater than or equal to the targetSum (7).
Example 2:
Input:{"nums":[1,4,4],"targetSum":4}
Output:1
Explanation: The contiguous subarray [4] has the minimal length of 1 and its sum (4) is greater than or equal to the targetSum (4).
Example 3:
Input:{"nums":[1,1,1,1,1,1,1,1],"targetSum":11}
Output:0
Explanation: There is no contiguous subarray whose sum is greater than or equal to the targetSum (11). The sum of all elements is 8, which is less than 11.
Constraints
- 1 <= nums.length <= 10^5
- 1 <= nums[i] <= 10^4
- 1 <= targetSum <= 10^9
Time: O(N) Space: O(1)
Use a sliding window. Initialize two pointers, `left` and `right`, at the beginning of the array. Expand the window by moving `right` and adding elements to the current sum. Once the sum is >= `targetSum`, update the minimum length and shrink the window by moving `left` and subtracting elements, until the sum is less than `targetSum` again. Repeat until `right` reaches the end of the array.
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
def min_window_sum(nums, target_sum):
if not nums:
return 0
min_length = float('inf')
current_sum = 0
left = 0
for right in range(len(nums)):
current_sum += nums[right]
while current_sum >= target_sum:
min_length = min(min_length, right - left + 1)
current_sum -= nums[left]
left += 1
return min_length if min_length != float('inf') else 0