Our June 2021 cohorts are filling up quickly. Join our free webinar to Uplevel your career # Sum Zero Problem

Given an array of integers, find any non-empty subarray whose elements sum up to zero.

##### Example One

Input: [5, 1, 2, -3, 7, -4]

Output: [1, 3]

Sum of [1, 2, -3] subarray is zero. It starts at index 1 and ends at index 3 of the given array, so [1, 3] is a correct answer. [3, 5] is another correct answer.

Example Two

Input: [1, 2, 3, 5, -9]

Output: [-1]

There is no non-empty subarray with sum zero.

##### Notes

Input Format: Function has one parameter, an integer array.

Output: Return an array of integers. If no zero sum subarray is found, return [-1]. Otherwise return [start_index, end_index] of a non-empty zero sum subarray; zero-based indices; both start_index and end_index are included in the subarray. If there are multiple such subarrays, any one is a correct answer.

● 1

● -10^9

#### Solutions:

We provided two solutions.

#### 1) brute_force_solution.java

A naive approach would be to iterate over all possible subarrays of input array arr, such that while on subarray [i,j], i.e. subarray starting from i-th index and ending at jth index, find sum of elements in it and if it's zero, return [i,j]. If no such subarray is found, return [-1].

##### Time Complexity:

O(n*n) where n is length of input arr.

As we are iterating over all possible subarrays of input array arr, time complexity will be O(n*n).

##### Auxiliary Space Used:

O(1).

We are not storing anything extra.

##### Space Complexity:

O(n) where n is length of input arr.

To store input it takes O(n) and as auxiliary space used is O(1).

Hence, O(n) + O(1) → O(n).

``````
// -------- START --------
static int[] sumZero(int[] arr) {
// To store interval (start, end) for which sum is zero
int[] res = new int;
// To store current sum
long sum = 0;
// We are trying to find sum of each subarray[i, n-1] where 0<=i<=n-1.
for (int i = 0; i < arr.length; i++) {
sum = 0;
// To calculate sum of subarray starting from i and ending at n-1
for (int j = i; j < arr.length; j++) {
sum += arr[j];
// If sum == 0 means we found our subarray having sum as 0 with start index i
// and end index j
if (sum == 0) {
res = i;
res = j;
return res;
}
}
}
// If no subarray as sum equal to zero found then we will return [-1]
return new int[]{-1};
}
// -------- END --------
``````

#### 2) optimal_solution.java

##### An optimal approach would be as follows:

Notice that if there exists a zero sum subarray [i,j] in a given input array arr, then prefix sum (denote it as prefix where prefix[k] = arr + arr + arr + ... + arr[k]) prefix[j] should be equal to prefix[i-1], as prefix[j] = prefix[i-1] + (arr[i] + arr[i+1] + ... + arr[j]), where the term in bracket is sum of subarray [i,j], which is 0.

Considering this fact, build prefix sum array prefix. If for some i, j, 0

##### Time Complexity:

O(n) where n is length of input arr.

To find out if any two sums of subarrays are equal or not we will store them in HashMap as prefix[k] (i.e. sum) as key and k as value. To maintain a hashmap it will take O(n) time complexity in the worst case to get and store n sums.

##### Auxiliary Space Used:

O(n) where n is length of input arr.

We are using hashmap to store sums. It will take O(n) of space.

##### Space Complexity:

O(n) where n is length of input arr.

To store input it takes O(n) and as auxiliary space used is O(n).

Hence, O(n) + O(n) → O(n).

``````
// -------- START --------
static int[] sumZero(int[] arr) {
// To store interval (start, end) for which sum is zero
int[] res = new int;
// To store prefix sum i.e. sum of subarray starting at index 0 and ending at index i
// Key of hashmap will be sum and value will be index i for prefix sum
HashMap map = new HashMap<>();
// To check whether prefix sum it self is equal to zero
map.put(0l, -1);
// To store current sum
long sum = 0;
for (int i = 0; i < arr.length; i++) {
// To check if we encountered with value which itself is zero
if(arr[i]==0){
res=i;
res=i;
return res;
}
// Adding current value in current sum
sum += arr[i];
// If we found value sum in our hashmap means we have encountered with this sum before
// means arr[0, map.get(sum)] = sum and
// arr[0, map.get(sum)] + arr[map.get(sum)+1, i] = sum
// which implies arr[map.get(sum)+1, i] = 0 and hence interval we are looking for is
// start = map.get(sum)+1 and end = i
if (map.containsKey(sum)) {
res = map.get(sum) + 1;
res = i;
return res;
} else {
map.put(sum, i);
}
}
// If no subarray having sum = 0 found then we will return [-1]
return new int[]{-1};
}
// -------- END --------
``````

### Try yourself in the Editor

Note: Input and Output will already be taken care of.

All Posts