Subarray Sum - Two Pointers / Prefix Sum

Problems
28

With the knowledge of the prefix sum under our belt, the problem boils down to Two Sum Sorted

This is incorrect. The problem then boils down two sum unsorted

29

The article says:

    prefix_sums = {0: 0}
    cur_sum = 0
    for i in range(len(arr)):
        cur_sum += arr[i]
        complement = cur_sum - target
        if complement in prefix_sums:
            return [prefix_sums[complement], i + 1]
        prefix_sums[cur_sum] = i + 1

And then

Note that in the implementation, typically we use `prefix_sum[i]` to denote the sum of elements in `0...i - 1` (rightmost element `i` is not included in the sum

Issues:

  1. These two statements contradict each other. One is using cur_sum as key, the other is using the index as the key.

  2. Using cur_sum as hashmap key is not a generic template solution, as cur_sum may not be unique.

I am assuming as the owner of this site, you still want to attract new members and buy your service.

But such confusion is not good for this site’s reputation and increasing your income.

30

Also, the prefix sum template returns an unnecessary zero due to initialization of the prefix sum array that is returned.

Below is an example of what it might look like to remove the zero from the returned array.

Removal of initialized prefix sum array


def prefix_sum_array(arr):
    prefix_sum = []
    current_sum = 0
    for num in arr:
        current_sum += num
        prefix_sum.append(current_sum)
    return prefix_sum