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.

Constraints:

● 1 <= n <= 5*10^5

● -10^9 <= arr[i] <= 10^9, (i = 0,1,...,(n-1))

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[2];
        // 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[0] = i;
                    res[1] = 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[0] + arr[1] + arr[2] + ... + 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 <= i <= j < n, prefix[i-1] = prefix[j], then subarray [i,j] is the zero sum subarray.

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[2];
        // 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[0]=i;
                res[1]=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[0] = map.get(sum) + 1;
                res[1] = 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 --------