Saturday, 16 July 2016

Largest sub array with sum equal to zero | Solution in Java

Hello Friends,

I am here with another famous algorithmic problem.

Given an Array of Integers, find the length of largest sub array such that the sum of the elements of the sub array is equal to zero. 

Points to ponder reading the problem statement.
  1. Array can contain negative elements, positive elements, zero.
  2. Array with all elements greater than zero will have zero sized Sub-Array. 
  3. With two loops it can be solved with below. Its Time complexity is O(n2). It can be optimized to O(n) but lets first see the solution which comes simple to the mind.
 SOLUTION 1 with Time complexity is O(n2)


public class ZeroSubArrayMaxLength {
    public static void main(String[] args) {
        int[] array = {-12,3,1,-2,-1,1,10,0};
        int result = maxLength(array);
        System.out.println(result);
    }
    public static int maxLength(int[] array) {
        int N = array.length;
        int sum = 0, localLen = 0;
        int maxLen = 0;
        for (int i = 0; i < N; i++) {
            sum = array[i];
            localLen = 1;
            if (sum == 0 && maxLen == 0) {
                maxLen = 1;
            }
            for (int j = i + 1; j < N; j++) {
                sum = sum + array[j];
                localLen++;
                if (sum == 0 && localLen > maxLen) {
                    maxLen = localLen;
                }
            }
        }
        return maxLen;
    }
}

 
Now lets try to design the optimized solution with time complexity of O(n).

Suppose there is a person who starts a business with zero savings and he records the total savings accumulated in his account each day. 
On day 1 he records S1, on day 2 he records S2.
On day 5 he losses the amount equal to sum of what he earned on day 3 and day 4

Quick Question!! What is the total savings he records on day 5 ?
Answer : S2 (As day 3, day 4 and day 5 were actually resulted in 0 profit 0 loss.)
Extending this idea, lets see below image:



Extending the idea further lets see below Approach:
 

[ Note as how the entry in Hash Map is only put when we encounter a new sum, for the sum already present ( as key in Hash Map ) only the length of the sub array is computed and max length is updated if the length of the sub array is greater ]. 
 
Now Lets write the code finally!!

import java.util.HashMap;

public class ZeroSubArrayMaxLength {
    public static void main(String[] args) {
        int[] array = { 7, -5, -2, -3, 2, 1, 10 };
        int result = maxLength(array);
        System.out.println(result);
    }

    public static int maxLength(int A[]) {
        int n = A.length;
        HashMap<Integer, Integer> hashMap = new HashMap<>();
        int sum = 0;
        int maxLength = 0;
        hashMap.put(0, -1); // initialization
        for (int i = 0; i < n; i++) {
            sum = sum + A[i];
            Integer pSumIndex = hashMap.get(sum);
            if (pSumIndex != null) {
                int localLength = i - pSumIndex;
                if (maxLength < localLength) {
                    maxLength = localLength;
                }
            } else {
                hashMap.put(sum, i);
            }
        }
        return maxLength;
    }
}