Maximum span in two arrays with equal sum

Question

This is programming puzzle. We have two arrays A and B. Both contains 0's and 1's only.

We have to two indices i, j such that

 a[i] + a[i+1] + .... a[j] = b[i] + b[i+1] + ... b[j]. 

Also we have to maximize this difference between i and j. Looking for O(n) solution.

I found O(n^2) solution but not getting O(n).

Answer 1

Best solution is O(n)

First let c[i] = a[i] - b[i], then question become find i, j, which sum(c[i], c[i+1], ..., c[j]) = 0, and max j - i.

Second let d[0] = 0, d[i + 1] = d[i] + c[i], i >= 0, then question become find i, j, which d[j + 1] == d[i], and max j - i.

The value of d is in range [-n, n], so we can use following code to find the answer

answer = 0, answer_i = 0, answer_j = 0
sumHash[2n + 1] set to -1
for (x <- 0 to n) {
  if (sumHash[d[x]] == -1) {
    sumHash[d[x]] = x
  } else {
    y = sumHash[d[x]]
    // find one answer (y, x), compare to current best
    if (x - y > answer) {
      answer = x - y
      answer_i = y
      answer_j = y
    }
  }
}

Answer 2

Here is an O(n) solution.

I use the fact that sum[i..j] = sum[j] - sum[i - 1].

I keep the leftmost position of each found sum.

    int convertToPositiveIndex(int index) {
        return index + N;
    } 

    int mostLeft[2 * N + 1];
    memset(mostLeft, -1, sizeof(mostLeft));

    int bestLen = 0, bestStart = -1, bestEnd = -1;

    int sumA = 0, sumB = 0;
    for (int i = 0; i < N; i++) {
        sumA += A[i];
        sumB += B[i];

        int diff = sumA - sumB;
        int diffIndex = convertToPositiveIndex(diff);

        if (mostLeft[diffIndex] != -1) {
            //we have found the sequence mostLeft[diffIndex] + 1 ... i
            //now just compare it with the best one found so far 
            int currentLen = i - mostLeft[diffIndex];
            if (currentLen > bestLen) {
                bestLen = currentLen;
                bestStart = mostLeft[diffIndex] + 1;
                bestEnd = i;
            }
        }

        if (mostLeft[diffIndex] == -1) {
            mostLeft[diffIndex] = i;
        }
    }

cout << bestStart << " " << bestEnd << " " << bestLen << endl;

P.S. mostLeft array is 2 * N + 1, because of the negatives.

Answer 3

This is a fairly straightforward O(N) solution:

let sa = [s1, s2, s3.. sn] where si = sum(a[0:i]) and similar for sb

then sum(a[i:j]) = sa[j]-sa[i] and sum(b[i:j]) = sb[j] - sb[i]

Note that because the sums only increase by 1 each time, we know 0 <= sb[N], sa[N] <=N

difference_array = [d1, d2, .. dn] where di = sb[i] - sa[i] <= N

note if di = dj, then sb[i] - sa[i] = sb[j] - sa[j] which means they have the same sum (rearrange to get sum(b[i:j]) and sum(a[i:j]) from above).

Now for each difference we need its max position occurrence and min position occurrence

Now for each difference di, the difference between max - min, is an i-j section of equal sum. Find the maximum max-min value and you're done.

sample code that should work:

a = []
b = []
sa = [0]
sb = [0]
for i in a:
    sa.append(sa[-1] + i)
for i in b:
    sb.append(sb[-1] + i)

diff = [sai-sbi for sai, sbi in zip(sa, sb)]
min_diff_pos = {}
max_diff_pos = {}
for pos, d in enumerate(diff):
    if d in min_diff_pos:
        max_diff_pos[d] = pos
    else:
        min_diff_pos[d] = pos

ans = min(max_diff_pos[d] - min_diff_pos[d] for d in diff)

Answer 4

Basically, my solution goes like this.

Take a variable to take care of the difference since the beginning.

int current = 0;
for index from 0 to length
    if a[i] == 0 && b[i] == 1
        current--;
    else if a[i] == 1 && b[i] == 0
        current++;
    else
        // nothing;

Find the positions where the variable has the same value, which indicates that there are equal 1s and 0s in between.

---

Pseudo Code:

Here is my primary solution:

int length = min (a.length, b.length);
int start[] = {-1 ... -1}; // from -length to length
start[0] = -1;
int count[] = {0 ... 0};   // from -length to length
int current = 0;
for (int i = 0; i < length; i++) {
    if (a[i] == 0 && b[i] == 1)
        current--;
    else if (a[i] == 1 && b[i] == 0)
        current++;
    else
        ; // nothing

    if (start[current] == -1) // index can go negative here, take care
        start[current] = current;
    else
        count[current] = i - start[current];
}
return max_in(count[]);