Donate : Link
Medium Blog : Link
Applications : Link
Problem: Given an unsorted array of nonnegative integers, find a continuous subarray.
Simple Approach
1) Traverse the array from Start to End.
2) From every index start another loop from (i+1) to the End of array.
To get all subarray starting from i, keep a variable "curSum" to calculate the sum.
3) For every index in inner loop update "curSum = curSum + array[j]".
4) If the curSum is equal to the given sum then print the subarray.Program
package com.test;
import java.util.Arrays;
/**
* @author code.factory
*/
public class SubarraySum {
public static void main(String... args) {
int array[] = new int[] {5, 8, 2, 3, 4, 1};
findSubArray(array, 5);
array = new int[] {2, 5, 30, 6, 15, 8};
findSubArray(array, 25);
array = new int[] {8, 20, 11, 6, 9};
findSubArray(array, 26);
}
private static void findSubArray(int array[], int sum) {
System.out.println(Arrays.toString(array));
int length = array.length;
int curSum = 0;
boolean flag = false;
for(int i=0; i<length; i++) {
curSum = array[i];
for(int j=i+1; j<=length; j++) {
if(curSum == sum) {
System.out.println("Sub array found b/w index " + i + " and " + (j-1));
flag = true;
}
if(curSum > sum || j == length) {
break;
}
curSum = curSum + array[j];
}
}
if(!flag) {
System.out.println("Sub array not found");
}
}
}
Output:
[5, 8, 2, 3, 4, 1] -> 5
Sub array found b/w index 0 and 0
Sub array found b/w index 2 and 3
Sub array found b/w index 4 and 5
[2, 5, 30, 6, 15, 8] -> 25
Sub array not found
[8, 20, 11, 6, 9] -> 26
Sub array found b/w index 2 and 4
Complexity Analysis:
- Time Complexity: O(n^2) in worst case.
Nested loop is used to traverse the array so the time complexity is O(n^2) - Space Complexity: O(1)
Constant extra space is required.
Efficient Approach
1) Create 3 variables curSum, start and end
2) Traverse the array and set "curSum = curSum + array[i]"
3) If curSum > sum then remove array[start] from curSum until curSum > sum AND start < i-1.
4) If curSum = sum then print subarray and set curSum, start and end variablesProgram
package com.test;
import java.util.Arrays;
/**
* @author code.factory
*/
public class SubarraySum {
public static void main(String... args) {
int array[] = new int[] {5, 8, 2, 3, 4, 1};
findSubArray(array, 5);
array = new int[] {2, 5, 30, 6, 15, 8};
findSubArray(array, 25);
array = new int[] {8, 2, 11, 6, 9};
findSubArray(array, 26);
array = new int[] {1, 4, 1};
findSubArray(array, 5);
array = new int[] {1, 4, 20, 3, 10, 5};
findSubArray(array, 33);
}
private static void findSubArray(int array[], int sum) {
System.out.println(Arrays.toString(array) + " -> " + sum);
int curSum = 0, start = 0, end = 0;
int length = array.length;
boolean flag = false;
for(int i=0; i<length; i++) {
if(i < length) {
curSum = curSum + array[i];
}
while(curSum > sum && start < i-1) {
curSum = curSum - array[start];
start = start + 1;
}
if(curSum == sum) {
end = i;
flag = true;
System.out.println("Sub array found b/w index " + start + " and " + end);
start = i;
if(i < length) {
curSum = array[i];
}
}
}
if(!flag) {
System.out.println("Sub array not found");
}
}
}
Output:
[5, 8, 2, 3, 4, 1] -> 5
Sub array found b/w index 0 and 0
Sub array found b/w index 2 and 3
Sub array found b/w index 4 and 5
[2, 5, 30, 6, 15, 8] -> 25
Sub array not found
[8, 2, 11, 6, 9] -> 26
Sub array found b/w index 2 and 4
[1, 4, 1] -> 5
Sub array found b/w index 0 and 1
Sub array found b/w index 1 and 2
[1, 4, 20, 3, 10, 5] -> 33
Sub array found b/w index 2 and 4
Complexity Analysis:
- Time Complexity: O(n)
Only one loop is used to traverse the array so the time complexity is O(n) - Space Complexity: O(1)
Constant extra space is required.
Handles Negative Numbers
1) Create HashMap to store key as curSum and value as i
2) Traverse the array and set "curSum = curSum + array[i]"
3) If (curSum - sum == 0) then print subarray with o to i
4) Check HashMap contains key (curSum - sum) then print subarray with hashMap[curSum-sum]+1 to i
5) Add curSum in hashMap as key and i as valueProgram
package com.test;
import java.util.Arrays;
import java.util.Map;
import java.util.TreeMap;
/**
* @author code.factory
*/
public class SubarraySum {
public static void main(String... args) {
int array[] = new int[] { 5, 8, 2, 3, 4, 1 };
findSubArray(array, 5);
array = new int[] { 2, 5, 30, 6, 15, 8 };
findSubArray(array, 25);
array = new int[] { 8, 2, 11, 6, 9 };
findSubArray(array, 26);
array = new int[] { 1, 4, 1 };
findSubArray(array, 5);
array = new int[] { 1, 4, 20, 3, 10, 5 };
findSubArray(array, 33);
array = new int[] { 10, 2, -2, -20, 10 };
findSubArray(array, -10);
array = new int[] { -10, 0, 2, -2, -20, 10 };
findSubArray(array, 20);
}
private static void findSubArray(int array[], int sum) {
System.out.println(Arrays.toString(array) + " -> " + sum);
int curSum = 0;
int start = 0;
int end = -1;
Map<Integer, Integer> hashMap = new TreeMap<>((e1, e2) -> e1 - e2);
for (int i = 0; i < array.length; i++) {
curSum = curSum + array[i];
if (curSum - sum == 0) {
start = 0;
end = i;
System.out.println("Sub array found b/w index " + start + " and " + end);
}
if (hashMap.containsKey(curSum - sum)) {
start = hashMap.get(curSum - sum) + 1;
end = i;
System.out.println("Sub array found b/w index " + start + " and " + end);
}
hashMap.put(curSum, i);
}
if (end == -1) {
System.out.println("Sub array not found");
}
}
}
Output:
[5, 8, 2, 3, 4, 1] -> 5
Sub array found b/w index 0 and 0
Sub array found b/w index 2 and 3
Sub array found b/w index 4 and 5
[2, 5, 30, 6, 15, 8] -> 25
Sub array not found
[8, 2, 11, 6, 9] -> 26
Sub array found b/w index 2 and 4
[1, 4, 1] -> 5
Sub array found b/w index 0 and 1
Sub array found b/w index 1 and 2
[1, 4, 20, 3, 10, 5] -> 33
Sub array found b/w index 2 and 4
[10, 2, -2, -20, 10] -> -10
Sub array found b/w index 0 and 3
Sub array found b/w index 3 and 4
[-10, 0, 2, -2, -20, 10] -> 20
Sub array not found
Your Code Academy 