Given an unsorted array of nonnegative integers, find a continous subarray which adds to a given number.
Examples:
Input: arr[] = {1, 4, 20, 3, 10, 5}, sum = 33
Ouptut: Sum found between indexes 2 and 4
Input: arr[] = {1, 4, 0, 0, 3, 10, 5}, sum = 7
Ouptut: Sum found between indexes 1 and 4
Input: arr[] = {1, 4}, sum = 0
Output: No subarray found
There may be more than one subarrays with sum as the given sum, return the first such subarray.
Solution 1. O(n^2) runtime: enumerate all possible subarrays and check if there is at least subarray that sums to the given sum.
Solution 2. O(n) runtime, O(1) space, using two pointers technique
1. Intialize a variable currSum as the first element arr[0], currSum indicates the sum of the current subarray.
2. Start from the second element, add each element one by one.
3. If currSum becomes equal to sum, return the current subarray's range. If currSum exceeds sum, then subtract trailing elements from currSum until currSum is no longer bigger than sum.
When subtracting the start element of a subarray, we need to ensure that after this step, there is still at least one element in currSum. Otherwise, this algorithm would break for the following corner case.
For the case of given sum 0 and all elements in currSum are bigger than 0:
currSum will be subtracted all the way to 0 as all elements are subtracted from it. start is the same with end now, indicating there is no element in currSum.
Since currSum == sum, this algorithm returns a range of start > end, which is wrong.
To fix this, we add another index check: start < end - 1 to ensure that we only do this subtraction when there are 2 or more elements in currSum.
or we loose this check condition to be start < end, so there can be no elements in currSum. Then if we have currSum == sum, we add another check start < end to make sure there is at least one element in currSum.
Either fix ensures that for a target sum of 0, the algorithm does not use an empty subarray as a matching answer.
Two pointers: start and end
start: the start index of the current subarray;
end: the next available element that can be added to the current subarray; the current subarray's end index is end - 1, not end.
1 public class SubarrayWithGivenSum { 2 public static int[] findSubarrayWithGivenSum(int[] arr, int sum) { 3 int[] range = new int[2]; 4 range[0] = -1; range[1] = -1; 5 if(arr == null || arr.length == 0 || sum < 0) { 6 return range; 7 } 8 int start = 0; 9 int currSum = arr[0]; 10 for(int end = 1; end <= arr.length; end++) { 11 while(currSum > sum && start < end - 1) { 12 currSum -= arr[start]; 13 start++; 14 } 15 if(currSum == sum){ 16 range[0] = start; 17 range[1] = end - 1; 18 break; 19 } 20 if(end < arr.length) { 21 currSum += arr[end]; 22 } 23 } 24 return range; 25 } 26 public static void main(String[] args) { 27 int[] arr1 = {1,4,20,3,10,5}; 28 int[] sub1 = findSubarrayWithGivenSum(arr1, 33); 29 for(int i = 0; i < 2; i ++) { 30 System.out.println(sub1[i]); 31 } 32 int[] arr2 = {1, 4}; 33 int[] sub2 = findSubarrayWithGivenSum(arr2, 0); 34 for(int i = 0; i < 2; i ++) { 35 System.out.println(sub2[i]); 36 } 37 } 38 }
1 public static int[] findSubarrayWithGivenSum(int[] arr, int sum) { 2 int[] range = new int[2]; 3 range[0] = -1; range[1] = -1; 4 if(arr == null || arr.length == 0 || sum < 0) { 5 return range; 6 } 7 int start = 0; 8 int currSum = arr[0]; 9 for(int end = 1; end <= arr.length; end++) { 10 while(currSum > sum && start < end) { 11 currSum -= arr[start]; 12 start++; 13 } 14 if(currSum == sum && start < end){ 15 range[0] = start; 16 range[1] = end - 1; 17 break; 18 } 19 if(end < arr.length) { 20 currSum += arr[end]; 21 } 22 } 23 return range; 24 }
Follow up question: Return all subarrays that add to the given number.
We must use solution 1 now as they are O(n^2) subarrays that sum up to the given number.
Example: an array of only 0s and a given sum of 0.