Friday, June 8, 2012

Find sub-sequence within array with sum = 0

A few days ago, I have been given a problem to find the sub-sequence within an array with which has a total sum of 0. Within array A[1-N], you have to find i and j such that
 A[i] + A[i+1]... A[j] = 0; i <=j.

Ofcourse, the problem can be extended further to find the longest subsequence among all possible sub-sequences. Once you have the solution for first part, finding longest sub-sequence is no more a tricky job.

This is what I thought:

The idea is: If sum of elements from [i+1, j] is 0, then, after this subset, ith number would appear again at [j+1] position.

i.e. Sum(N[i] + N[i+1, j]) = N[j + 1], if N[i+1, j] = 0.


   1. Sum elements such that ith index has sum up to [0 -i] elements
       For i = 1 to N
       Array[i] += Array[i -1]

   2. Find the first duplicate index from array
       EndIndex = FindFirstDuplicateIndex(Array)

   3. IF EndIndex > -1
       Find the First index with value equal to Array[EndIndex]
       For i = 0 to N
         IF(Array[i] == Array[EndIndex]
           StartIndex = i

   4. Return StartIndex and EndIndex as sub array indexes.

Running time of the algorithm is O(n) (though it slowly depends on the running time of FindFirstDuplicateIndex method which could be implemented in O(n) time).