[LeetCode] Minimum Size Subarray Sum

Minimum Size Subarray Sum

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn't one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

click to show more practice.

More practice:

If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Naive solutions:

1). The most naive solution will take O(n^3) time using constant space, since there are O(n^2) subarrays nums[i...j] (inclusive), and computing the sum for each subarray takes O(j - i + 1) time.

2). An optimized solution (compared with the above one) takes O(n^2) time using constant space. We divide O(n^2) subarrays into n groups by their lengths. For each group, we can compute all the sums in O(n) time by removing the first element in the previous sum and adding a new element in the end.

3). Alternatively, we can first compute all the prefix sums, where prefixSum[i] denotes the sum of the first i integers, i >= 0. Under this notation, the index for the prefixSum array ranges from 0 to n. Then we can simply iterative over all O(n^2) pairs, and the sum of all the elements in the subarray nums[i...j]  (inclusive) is simply prefixSum[j] - prefixSum[i - 1]. This takes O(n^2) time and extra O(n) space.

Below are more interesting and elegant solutions.

Solution 1: O(n) running time, and extra O(n) space.
We first compute all the prefix sums, where prefixSum[i] denotes the sum of the first i integers, i >= 0. Under this notation, the index for the prefixSum array ranges from 0 to n.
Next, we move two pointers i and j. For each i, we find the minimum length of a subarray starting from i + 1 (inclusive) of which the sum >= s. The key observation is that j is non-decreasing, which implies an algorithm with O(n) running time.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46

public class Solution { private int buildPrefixSum(int[] nums, int[] prefixSum) { prefixSum[0] = 0; for (int i = 0; i < nums.length; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } return prefixSum[nums.length]; } private int twoPointerIncrementalSearch( int s, int[] prefixSum ) { int minLen = prefixSum.length - 1; int i = 0; int j = 1; while ( i < prefixSum.length - 1 && j < prefixSum.length ) { if (prefixSum[j] - prefixSum[i] < s) { j++; } else { if (minLen > j - i) { minLen = j - i; } i++; } } return minLen; } public int minSubArrayLen(int s, int[] nums) { if (nums.length == 0) { return 0; } int[] prefixSum = new int[nums.length + 1]; int totalSum = buildPrefixSum(nums, prefixSum); if (totalSum < s) { return 0; } return twoPointerIncrementalSearch(s, prefixSum); } }

Solution 2: O(n) running time, and constant space.

For each i, we find the minimum length of a subarray starting from i (inclusive) of which the sum >= s. The key observation is that we can update the current sum of all the elements in the subarray nums[i ... j] (inclusive) in constant time each step, and furthermore, j is non-decreasing, which implies an algorithm with O(n) running time.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36

public class Solution { public int minSubArrayLen(int s, int[] nums) { if (nums.length == 0) { return 0; } int totalSum = 0; for (int num : nums) { totalSum += num; } if (totalSum < s) { return 0; } int i = 0; int j = 0; int currSum = nums[0]; int minLen = nums.length; while (i < nums.length) { if (currSum >= s) { if (minLen > j - i + 1) { minLen = j - i + 1; } currSum -= nums[i]; i++; } else { j++; if (j >= nums.length) { break; } currSum += nums[j]; } } return minLen; } }

Solution 3: O(n log n) running time, and extra O(n) space.
We first compute all the prefix sums, where prefixSum[i] denotes the sum of the first i integers, i >= 0. Under this notation, the index for the prefixSum array ranges from 0 to n.
Next, for each index i, we find the minimum length of a subarray starting from i + 1 (inclusive) of which the sum >= s, using binary search. Hence, the overall running time is O(n log n). 
Remarks: A slight improvement in terms of performance will be narrowing down the range of the binary search even further. Instead of searching from i to end, one can search from j to end, where j > i. One needs to change the following binarySearch() function signature to incorporate this improvement.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50

public class Solution { private int buildPrefixSum(int[] nums, int[] prefixSum) { prefixSum[0] = 0; for (int i = 0; i < nums.length; i++) { prefixSum[i + 1] = prefixSum[i] + nums[i]; } return prefixSum[nums.length]; } private int binarySearch(int i, int s, int[] prefixSum) { int low = i; int high = prefixSum.length - 1; while (low <= high) { int mid = low + (high - low) / 2; if (prefixSum[mid] - prefixSum[i] < s) { low = mid + 1; } else { if ( mid > 0 && prefixSum[mid - 1] - prefixSum[i] < s ) { return mid - i; } high = mid - 1; } } return prefixSum.length; } public int minSubArrayLen(int s, int[] nums) { if (nums.length == 0) { return 0; } int[] prefixSum = new int[nums.length + 1]; int totalSum = buildPrefixSum(nums, prefixSum); if (totalSum < s) { return 0; } int minLen = prefixSum.length - 1; for (int i = 0; i < prefixSum.length; i++) { int len = binarySearch(i, s, prefixSum); if (minLen > len) { minLen = len; } } return minLen; } }