Given an array of positive and negative numbers, find if there is a subarray with 0 sum.
Key Idea: Prefix Sum, and hashtable, space for time.
We will have to use hashmap.
This can be extend to solve subarray with N.
http://www.geeksforgeeks.org/amazon-interview-set-68-for-sde-1/
1. Given an array of integers (+ve and -ve), give a contiguous set of numbers that add to N
http://stackoverflow.com/questions/5534063/zero-sum-subarray
Related:
http://likemyblogger.blogspot.com/2015/09/mj-38-target-sum.html
Given an array A, determine if there is a subarray with sum equal to a given target.
Eg., if A = {4, 7, -5, 6, -2, 1} and target = 8. It should return true because sum{7, -5, 6} = 8. If target = 3, it should return false.
Read full article from Find if there is a subarray with 0 sum | GeeksforGeeks
Key Idea: Prefix Sum, and hashtable, space for time.
We will have to use hashmap.
This can be extend to solve subarray with N.
http://www.geeksforgeeks.org/amazon-interview-set-68-for-sde-1/
1. Given an array of integers (+ve and -ve), give a contiguous set of numbers that add to N
http://stackoverflow.com/questions/5534063/zero-sum-subarray
This algorithm will find all subarrays with sum 0 and it can be easily modified to find the minimal one or to keep track of the start and end indexes. This algorithm is O(n).
Given an
int[] input array, you can create an int[] tmp array where tmp[i] = tmp[i - 1] + input[i]; Each element of tmp will store the sum of the input up to that element.
Now if you check tmp, you'll notice that there might be values that are equal to each other. Let's say that this values are at indexes
j an k with j < k, then the sum of the input till j is equal to the sum till k and this means that the sum of the portion of the array between j and k is 0! Specifically the 0 sum subarray will be from index j + 1 to k.- NOTE: if
j + 1 == k, thenk is 0and that's it! ;) - NOTE: The algorithm should consider a virtual
tmp[-1] = 0; - NOTE: An empty array has sum 0 and it's minimal and this special case should be brought up as well in an interview. Then the interviewer will say that doesn't count but that's another problem! ;)
The implementation can be done in different ways including using a HashMap with pairs but be careful with the special case in the NOTE section above.
Example:
int[] input = {4, 6, 3, -9, -5, 1, 3, 0, 2}
int[] tmp = {4, 10, 13, 4, -1, 0, 3, 3, 5}
- Value 4 in tmp at index 0 and 3 ==> sum tmp 1 to 3 = 0, length (3 - 1) + 1 = 4
- Value 0 in tmp at index 5 ==> sum tmp 0 to 5 = 0, length (5 - 0) + 1 = 6
- Value 3 in tmp at index 6 and 7 ==> sum tmp 7 to 7 = 0, length (7 - 7) + 1 =
static Boolean printZeroSumSubarray(int arr[]) { // Creates an empty hashMap hM HashMap<Integer, Integer> hM = new HashMap<Integer, Integer>(); // Initialize sum of elements int sum = 0; // Traverse through the given array for (int i = 0; i < arr.length; i++) { // Add current element to sum sum += arr[i]; // Return true in following cases // a) Current element is 0 // b) sum of elements from 0 to i is 0 // c) sum is already present in hash map if (arr[i] == 0 || sum == 0 || hM.get(sum) != null) return true; // Add sum to hash map hM.put(sum, i); } // We reach here only when there is no subarray with 0 sum return false; }http://likemyblogger.blogspot.com/2015/09/mj-38-target-sum.html
Given an array A, determine if there is a subarray with sum equal to a given target.
Eg., if A = {4, 7, -5, 6, -2, 1} and target = 8. It should return true because sum{7, -5, 6} = 8. If target = 3, it should return false.
bool findTargetSum(vector<int> &nums, int target){ unordered_set<int> partialSum; int sum = 0; for(auto n:nums){ sum += n; if(partialSum.find(sum-target)!=partialSum.end()){ return true; } partialSum.insert(sum); } return false;}