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).
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).
Here is one of the possible implementation of the above algorithm. Running time of the implemented algorithm is O(n).
ReplyDeleteprivate 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;
}