mediumSliding WindowPattern: Sliding Window
Minimum Window Sum Solution
Problem Statement
You are given an array of integers `arr` and a target integer `target`. Find the shortest continuous subarray where the total sum is at least `target`. If no such subarray exists, return 0.
Examples
Example 1:
Input:{"arr":[1,2,3,4,5],"target":7}
Output:2
Explanation: The subarray [2, 3, 4] has sum 9 which is greater than the target 7, and the subarray [3, 4] has sum 7 which equals the target 7. Therefore, the shortest window is of length 2.
Example 2:
Input:{"arr":[1,2,3,4,5],"target":15}
Output:5
Explanation: The sum of the whole array [1, 2, 3, 4, 5] equals 15. Therefore, the length of the shortest window is 5.
Example 3:
Input:{"arr":[1,2,3,4,5],"target":20}
Output:0
Explanation: The sum of the whole array [1, 2, 3, 4, 5] is 15, which is less than 20. Therefore, the output is indeed 0, because it's impossible to find a subarray with sum at least 20.
Constraints
- 1 <= n <= 10^5
- 1 <= arr[i] <= 10^4
- 1 <= target <= 10^9
Time: O(N) Space: O(1)
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).
Run, Test & Submit Code
Ready to practice this challenge? Launch our interactive compilation environment with compiler validation.
Solve on Interactive WorkspaceTested Solutions
No solution code is currently loaded.
Complete this code in the workspace editor.