I have seen solutions online but all of the solutions have either O(n) or O(n^2) time complexity. I wondering if it is possible to find the subarray with sum 0 in O(nlogn) that uses no auxiliary data structure. However, we are allowed to use recursion.
Can we modify the Maximum Subarray Sum algorithm to find the solution to this problem?
The input array will have just 1's and -1's and the algorithm will find a subarray with sum 0.
Input = { 1, 1, -1, 1, -1, -1, 1, -1}
output = 1, 8 (1 being the starting index and 8 being the last index)
In this particular case, the whole input array has the sum equals to 0. So, the starting and the ending indexes reported are 1 and 8 respectively(assuming that the indexing in the array starts from 1).
Edit: We can use the solution to this problem to solve another problem. That problem is as follows.
Given an array arr of n integers, find the longest contiguous sub-array with an equal number of even and odd elements. Following is an example (indexing starts from 1):
A = {8, 2, -3, 4, 9, 6}
Answer: (2, 5). (2 being the starting index and 5 being the last index)
The only constraint is that the algorithm can't use any auxiliary data structure. The solution has to be most efficient under this constraint. Also, using recursion is allowed.
You could use a recursive algorithm where the function gets the value of the previous array value (if any) and then reads the next value from the input array. If it is the same value, then it calls itself recursively and when coming back from there, it continues with the next value in the same way. If it is the opposite value it returns to the caller true -- to indicate that there was a zero sum. If the end of the array is encountered, the function returns false.
This practically means that the depth of recursion is equal to the absolute cumulative sum. So for instance, if the array is [-1, -1, -1, 1], then the recursion will go to depth 3, and it will return from level 3 to level 2 with return value true. At level 2 it will return false since the end of the array was encountered, and so it will fall out of recursion.
Whenever the return value is true, you can check if the covered interval is greater in size than so far encountered.
Here is an implementation of this idea in JavaScript:
function zeroSum(arr) {
let i = 0; // index in the input array, managed outside of recursion
// Longest zero-sum interval so far. Zero based, and value at end index
// is not part of the interval:
let longest = [0, 0];
function recur(dir) { // dir is the previous value from the array (if any)
let start = i; // local variable
while (i < arr.length) {
let val = arr[i++];
if (val == -dir) return true; // zero sum
if (recur(val) && i - start > longest[1] - longest[0]) {
longest[0] = start;
longest[1] = i;
}
}
return false; // no zero sum
}
recur(0); // 0 is passed to indicate there is no previous value
return longest;
}
// demo
console.log(zeroSum([1, 1, -1, 1, -1, -1, 1, -1]));