Given an array of n positive integers and a positive integer s, find the minimal length of a contiguous subarray of which the sum ≥ s.
Example
I: nums = [2,3,1,2,4,3], s = 7
O: 7 because [4,3]
Analysis
The brute force approach is just to try all possible subarrays then keep the shortest length.
Code
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int currentSum = 0;
int minLength = Integer.MAX_VALUE;
// from this number the smallest window
for (int i = 0; i < nums.length; i++) {
currentSum = 0;
for (int j = i; j < nums.length; j++) {
currentSum += nums[j];
if (currentSum >= s) {
minLength = Math.min(minLength, j - i + 1);
break;
}
}
}
return (minLength == Integer.MAX_VALUE) ? 0 : minLength;
}
Optimization
The brute force solution is O(n^2) because the pointer j will go back to where i is for every nested loop. The best way to see the overlapping subproblems is to run through some examples.
[2,3,1,2,4,3], 7
A 2 3 1 2 4 3
L1 i j
L2 i j <--we already know this won't be a solution
-j should at least start from index 3
j doesn't have to go back to i every time. Instead of scanning every window, we "shrink" the window then extend it on the other end.
We want to shrink then extend but this won't work for the first iteration. So instead we want to shrink before we get to the next iteration.
public int minSubArrayLen(int s, int[] nums) {
if (nums == null || nums.length == 0) {
return 0;
}
int currentSum = 0;
int minLength = Integer.MAX_VALUE;
int j = 0;
// from this number the smallest window
for (int i = 0; i < nums.length; i++) {
// extend the window
while (j < nums.length && currentSum < s) {
currentSum += nums[j++];
}
// check the window sum
if (currentSum >= s) {
int windowSize = j - i; // no +1 b/c j++ after fit window
minLength = Math.min(minLength, windowSize);
}
// shrink before next iteration
currentSum -= nums[i];
}
return (minLength == Integer.MAX_VALUE) ? 0 : minLength;
}
