Problem
This problem is variant of Minimum Size Subarray Sum Problem
Solution
Method 1 - Brute Force
This is similar to the brute force approach we discussed for the original problem. The only difference is that we’re checking if the subarray sum is equal to K
instead of greater than or equal to K
.
Code
Java
public class Solution {
private static int minSubArrayLenWithSumK(int[] a, int K) {
int n = a.length;
int ans = Integer.MAX_VALUE;
for(int i = 0; i < n; i++) {
int currSubarraySum = 0;
for(int j = i; j < n; j++) {
currSubarraySum += a[j];
if(currSubarraySum == K) {
ans = Math.min(ans, j-i+1);
break;
}
if(currSubarraySum > K) {
break;
}
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
Complexity
- ⏰ Time complexity:
O(n^2)
- 🧺 Space complexity:
O(1)
Method 2 - Sliding Window
The sliding window implementation of this variation is also similar to the implementation of the original problem. The difference is that we update the minimum length only when the windowSum
is equal to K
.
Code
Java
public class Solution {
private static int minSubArrayLenWithSumK(int[] a, int K) {
int n = a.length;
int ans = Integer.MAX_VALUE;
int windowSum = 0;
int left = 0;
for(int right = 0; right < n; right++) {
windowSum += a[right];
while(windowSum > K) {
windowSum -= a[left];
left++;
}
if(windowSum == K) {
ans = Math.min(ans, right-left+1);
}
}
return ans == Integer.MAX_VALUE ? 0 : ans;
}
}
Complexity
- ⏰ Time complexity:
O(n)
- 🧺 Space complexity:
O(1)