Subarray with sum zero

Subarray with sum zero

Given an array of positive and negative integers, find a subarray with sum zero in that array. For example, in the array given below, there are two subarrays whose elements sum to zero.

subarray with sum zero
Input array
Array highlighted adds up to zero
subarray with zero sum

Brute force method to find subarray with sum zero will be to find all sub-arrays of the array and then add them individually to see if any subarray adds up to zero. There can be n * (n-1) subarrays for a given array of size n, so the complexity of brute force solution is O(n2).

package com.company;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by sangar on 3.12.18.
 */
public class SubarrayWithZeroSum {
    public int [] findSubarrayWithZeroSumBrute(int[] a){
        int len = a.length;

        for(int i=0; i<len; i++){
            int  sum  = 0;
            for(int j=i; j<len; j++){
                sum += a[j];
                if(sum == 0){
                    return Arrays.copyOfRange(a,i,j+1);
                }
            }
        }
        return new int[0];
    }
}

Test cases

package test;

import com.company.SubarrayWithZeroSum;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static org.junit.Assert.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class SubarrayWithSumZeroTest {

    SubarrayWithZeroSum tester = new SubarrayWithZeroSum();

    @Test
    public void subarrayWithZeroSumBruteTest() {

        int[] a = {2, -3, -1, 4};
        int [] output = {-3, -1, 4};
        assertEquals(Arrays.toString(output),
              Arrays.toString(tester.findSubarrayWithZeroSumBrute(a)));
    }

    @Test
    public void subarrayWithZeroSumBruteNoSubArrayTest() {

        int[] a = {2, -3, -2, 4};
        int [] output = {};
        assertEquals(Arrays.toString(output),
              Arrays.toString(tester.findSubarrayWithZeroSumBrute(a)));
    }

    @Test
    public void subarrayWithZeroSumBruteOneElementTest() {

        int[] a = {2, 0, -1, 4};
        int [] output = {0};
        assertEquals(Arrays.toString(output),
              Arrays.toString(tester.findSubarrayWithZeroSumBrute(a)));
    }
}

Find subarray with sum zero: thoughts

A subarray is a contiguous part of an array. Let’s say we find the sum of subarray starting at 0 and ending at any index i. So, T[i] represents the sum of subarray A[0..i].

What if we have two indices i and j; such that i< j and T[i] = T[j]. In this case, all the elements which are between index i and index j add up to zero and that is our subarray with sum zero.
Length of subarray with sum zero will be j-i+1.

Implementation

package com.company;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by sangar on 3.12.18.
 */
public class SubarrayWithZeroSum {
    public int [] findSubarrayWithZeroSum(int[] a){

        int len = a.length;

        int [] T = new int[len];

        T[0] = a[0];
        for(int i=1; i<len; i++){
            T[i] = T[i-1] + a[i];
        }

        //Complexity of below code is O(n^2)

        for(int i=0; i<len; i++){
            for(int j=i+1; j<len; j++){
                if(T[i]== T[j]){
                    return Arrays.copyOfRange(a, i+1, j+1);
                }
            }
        }
        return new int[0];
    }
}

Test cases

package test;

import com.company.SubarrayWithZeroSum;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static org.junit.Assert.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class SubarrayWithSumZeroTest {

    SubarrayWithZeroSum tester = new SubarrayWithZeroSum();

    @Test
    public void subarrayWithZeroSumTest() {

        int[] a = {2, -3, -1, 4};
        int [] output = {-3, -1, 4};
        assertEquals(Arrays.toString(output),
                Arrays.toString(tester.findSubarrayWithZeroSum(a)));
    }

    @Test
    public void subarrayWithZeroSumNoSubArrayTest() {

        int[] a = {2, -3, -2, 4};
        int [] output = {};
        assertEquals(Arrays.toString(output),
                Arrays.toString(tester.findSubarrayWithZeroSum(a)));
    }

    @Test
    public void subarrayWithZeroSumOneElementTest() {

        int[] a = {2, 0, -1, 4};
        int [] output = {0};
        assertEquals(Arrays.toString(output),
                Arrays.toString(tester.findSubarrayWithZeroSum(a)));
    }

The complexity of the algorithm to find a subarray with zero sum in a given array of integers is O(n2) with an additional space complexity of O(n) to store sum till index i.

We can optimize it further by creating a hash of all the sums which we see while adding. When we add the index i to already calculated sum till index i-1, we check if the new sum is zero? If yes, then subarray from 0 to index i add up to zero. If there is already a sum present which is equal to the current sum then there is subarray with sum zero between index when we saw the sum last and current index.

package com.company;

import java.util.Arrays;
import java.util.HashMap;

/**
 * Created by sangar on 3.12.18.
 */
public class SubarrayWithZeroSum {

    public int [] findSubarrayWithZeroSumOptimized(int[] a){

        int len = a.length;

        HashMap<Integer, Integer> T = new HashMap<Integer, Integer>();

        int sum  = 0 ;
        for(int i=0; i<len; i++){
            sum  += a[i];
            if(T.get(sum) != null){
                return Arrays.copyOfRange(a,T.get(sum)+1, i+1);
            }
            T.put(sum, i);
        }

        return new int[0];
    }
}

Test cases

package test;

import com.company.SubarrayWithZeroSum;
import org.junit.jupiter.api.Test;

import java.util.Arrays;

import static org.junit.Assert.assertEquals;

/**
 * Created by sangar on 23.9.18.
 */
public class SubarrayWithSumZeroTest {

    SubarrayWithZeroSum tester = new SubarrayWithZeroSum();

    @Test
    public void subarrayWithZeroSumOptimizedTest() {

        int[] a = {2, -3, -1, 4};
        int [] output = {-3, -1, 4};
        assertEquals(Arrays.toString(output),
          Arrays.toString(tester.findSubarrayWithZeroSumOptimized(a)));
    }

    @Test
    public void subarrayWithZeroSumOptimizedNoSubArrayTest() {

        int[] a = {2, -3, -2, 4};
        int [] output = {};
        assertEquals(Arrays.toString(output),
          Arrays.toString(tester.findSubarrayWithZeroSumOptimized(a)));
    }

    @Test
    public void subarrayWithZeroSumOptimizedOneElementTest() {

        int[] a = {2, 0, -1, 4};
        int [] output = {0};
        assertEquals(Arrays.toString(output),
          Arrays.toString(tester.findSubarrayWithZeroSumOptimized(a)));
    }

}

The complexity of this method is O(n) with additional space of O(n) in worst case.

Please share if there is something wrong or missing. If you are preparing for an interview, please signup for free interview kit.