SubArray Sum | nuttynana

Software Engineer Interview Questions (2) | nuttynana
Given an array of integers eg [1,2,-3,1] find whether there is a sub-sequence that sums to 0 and return it (eg 1,2,-3 or 2,-3,1) Checking every sub-sequence is O(n^2) which is too inefficient

For all the sub-sequence problem, one trick is to use Cumulative sum.

For example, the cumsum of [1,2,-3,1] is [0,1,1+2,1+2-3,1+2-3+1] = [0,1,3,0,1]

The power of cumsum, is once you have it, you can easily get the sum of any sub-sequence. For example, let a be the original array, b be the cumsum of a. To calculate sum of a[i..j], instead of adding j-i+1 numbers, we only need 1 subtract b[j+1]-b[i]. This is because

b[j+1]-b[i]=(a[1]+a[2]+...+a[j])-(a[1]+a[2]+...+a[i-1])
           =a[i]+a[i+1]+...+a[j].

To get the cumsum is O(N). Once we have that, we need to find i, j, where a[i]+…+a[j] is 0. That means b[j+1]-b[i]=0, which means b[j+1] and b[i] are equal.

So the problem is to find two equal numbers in array b. Usually there are 2 solutions.

Solution two: Use a hash table. Just scan b from left to right and put whatever you have seen in to a hash table. Before you put it, check if it was already there. This is O(N) assume the hash code is not that bad. When doing the coding, we don’t have to construct array b explicitly. Here is the code in C++

void find(vector a) {
  int cumsum = 0;
  unordered_map<int, int> seen;
  seen[0] = 0;
  for (int i = 0; i < a.size(); ++i) {
    cumsum += a[i];
    auto it = seen.find(cumsum);
    if (it == seen.end()) {
      seen[cumsum] = i + 1;
    } else {
      cout << it->second << " " << i << endl;
      return;
    }
  }
  cout << "no found" << endl;
}

Read full article from Software Engineer Interview Questions (2) | nuttynana