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.


FindZeroSumSequence(Array):
{

   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
           Break


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

1 comment:

  1. Here is one of the possible implementation of the above algorithm. Running time of the implemented algorithm is O(n).

    private static void FindZeroSumSequence(int[] numbers, out int startIndex, out int endIndex)
    {
    startIndex = -1;
    endIndex = -1;

    if (numbers[0] != 0)
    {
    // Sum elements such that ith index should be having Sum Upto [0 -i] element.
    for (int i = 1; i < numbers.Length; i++)
    {
    numbers[i] += numbers[i - 1];
    }

    // Now, Find the first duplicate number in the array
    // Idea is: If sum of elements after ith index is 0, then, after the subset, number would appear again.
    // i.e. N[i] + N[i+1, j] = N[i], if N[i+1, j] = 0.
    endIndex = FindFirstDuplicateIndex(numbers);

    if (endIndex > -1)
    {
    for (int i = 0; i < endIndex; i++)
    {
    if (numbers[i] == numbers[endIndex])
    {
    startIndex = i + 1;
    break;
    }
    }
    }
    }
    else
    {
    // very first element is zero, which satisfies the criteria.
    // This would be one of the possible results if we are looking for max length subarray.
    // Here, we are just interested in first sub array summing to 0.
    startIndex = 0;
    endIndex = 0;
    }
    }

    ///
    /// This method finds the first duplicate number in the array.
    /// This is memory intensive sinc attempt was to complete the operation in O(n) time.
    /// Same can be done using construction of BST which will take O(n lgn), but less memory intensive
    ///
    private static int FindFirstDuplicateIndex(int[] numbers)
    {
    int maxValue = 0;
    int minValue = 0;
    int duplicateIndex = -1;

    // Find the Min Value and Max Value for bucket size.
    // We need minimum since array may contain negative numbers as well.
    for (int i = 0; i < numbers.Length; i++)
    {
    if (numbers[i] > maxValue)
    {
    maxValue = numbers[i];
    }
    else if (numbers[i] < minValue)
    {
    minValue = numbers[i];
    }
    }

    if (minValue < 0)
    {
    // Offset to shift the index
    minValue = Math.Abs(minValue);
    }

    // Get the bucket
    int[] bucket = new int[maxValue + minValue];

    for (int i = 0; i < numbers.Length; i++)
    {
    if (bucket[numbers[i] + minValue] == 1)
    {
    //This index in the bucket was already set.
    // We have seen this number.
    duplicateIndex = i;
    break;
    }
    else
    {
    bucket[numbers[i] + minValue] = 1;
    }
    }

    return duplicateIndex;
    }

    ReplyDelete