About usWhy usInstructorsReviewsCostFAQContactBlogRegister for Webinar
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.

Constraints:

● 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[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

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 --------


Try yourself in the Editor

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

Recommended Posts

All Posts