Showing posts with label How to find the largest subarray with sum 0. Show all posts
Showing posts with label How to find the largest subarray with sum 0. Show all posts

How to find the largest subarray with sum 0

Given an array of integers, find the largest subarray with sum equals to 0. If theres no subarray with sum 0 then print as "No subarray with sum 0".
How to find the largest subarray with sum 0
As solution we are going to iterate the give array from 0th index to nth index and sum each values and finding the subarray.
Solution:
  • Iterating from starting to end of the array
  • Iterating sub array from 'start' to 'end' pointer and break if sum zero got or sub array smaller than previous sub array with zero 
Lets see simple java code


public class SubArrayZero {

 public static void main(String[] args) {

  int array[] = new int[] { 15, -2, 2, -8, 0, 1, 7, 10, 23 };

  SubArrayZero obj = new SubArrayZero();

  obj.getSubArraySumZero(array);
 }
 
 public void getSubArraySumZero(int[] array) {

  int start = 0, end = 0, sum = 0, fStart = 1, fEnd = -1;

  // Iterating from starting to end of the array
  for (int i = 0; i < array.length; i++) {

   end = i;
   sum += array[i];

   if (sum == 0) {
    if ((fEnd - fStart) < (end - start)) {
     fStart = start;
     fEnd = end;
    }
   } else {
    int tSum = sum;
    
    /* Iterating sub array from 'start' to 'end' pointer and break
    *  if sum zero got or sub array smaller than previous sub array with zero 
    */
    for (int j = start; j < end; j++) {
     tSum -= array[j];
     if (tSum == 0) {
      if ((fEnd - fStart) < (end - (j + 1))) {
       fStart = j + 1;
       fEnd = end;
      }
      break;
     } else if ((fEnd - fStart) > (end - (j + 1)))
      break;
    }
   }
  }
  if(fEnd != -1) {
   System.out.println("Start Index : " + fStart);
   System.out.println("End Index   : " + fEnd);
  }else {
   System.out.println("No subarray with sum 0");
  }
 }
}

OUTPUT:


Start Index : 1
End Index   : 6