Subarray Sum - Two Pointers / Prefix Sum

Hi, I think I am missing something. I do understand the solution. However, I don’t see how it is related to two pointers. Can someone help me?

def subarray_sum(arr, target):
left, right = 0, 0
total_sum = 0
n = len(arr)

while left < n:
    while right < n:
        right += 1
        total_sum = sum(arr[left:right+1])
        if total_sum == target:
            return [left, right+1]
    right = left + 1
    left = right

It’s technically 1 point with hashmap but included in the two pointers section cuz of the similarity of moving pointers.

Nitpick: Problem states “It’s guaranteed to have a unique solution.” However, the example in the slides, arr=[1, 3, -3, 8, 5, 7], k=5, technically has 2 solutions [-3, 8] and [5].

why are we doing
–>complement = cur_sum - target
and not
–>complement = target-cur_sum

because previous_cur_sum + target = cur_sum

I solved this with two pointers and it passed all test cases. What am I missing?
def subarray_sum(arr: List[int], target: int) → List[int]:
l, r, total = 0, 0, 0

while r < len(arr):
    total += arr[r]
    if total == target:
        return [l, r + 1]
    elif total > target:
        while total > target:
            total -= arr[l]
            l += 1
            if total == target:
                return [l, r + 1]
    r += 1
return []

Your solution assumes that numbers are positive.

total -= arr[l] does not really work for negative numbers very well.

I think you need to run this on more edge cases.

Solution in JavaScript using while loop:

function subarraySum(arr, target) {
let fast = 0, slow = 0, sum = 0;

while (slow < arr.lengh || fast <= arr.length){
    if (sum < target) sum += arr[fast++];
    else if (sum > target) sum -= arr[slow++];
    else if (sum === target) return [slow, fast];
return [-1];


Tests are incomplete.

10 5 -5 -20 10

showed a big bug in my implementation.

The java implementation consistently seems to reverse the key and value. It is better to have key=index, value=sum for prefixSums, since the sums are not guaranteed to be unique

public static int subarraySumTotal(List<Integer> arr, int target) {
        Map<Integer, Integer> prefixSum = new HashMap<>();
        prefixSum.put(0, 1);
        int currentSum = 0;
        int counter = 0;
        for (int i = 0; i < arr.size(); i++) {
            currentSum += arr.get(i);
            int complement = currentSum - target;
            if(prefixSum.containsKey(complement) && prefixSum.get(complement) > 0) {
                counter += prefixSum.get(complement);
            if(prefixSum.containsKey(currentSum)) {
                prefixSum.put(currentSum, prefixSum.get(currentSum) + 1);
            } else {
                prefixSum.put(currentSum, 1);
        return counter;

what target value are you using?

I think they did that to reduce the time complexity as hashmap.containsValue() is o(n) while hashmap.containsKey() is o(1). If the sums are not unique, a larger index will overwrite a smaller index. If the sum is not the complementary, then it has no affect on results; if the sum is the complementary being looked for, then the solution returns the shortest subarray. As the question just asks for A solution but not all solutions so it’s fine.
But I totally agree with your question, I also had these questions when looking at their solution. I’d appreciate if the team can be better job explanation the solution.

O(N) solution:

def subarray_sum(arr: List[int], target: int) → List[int]:
left, right = 0, 1
sub_sum = arr[left] + arr[right]
res = []

while right <= len(arr):
    if sub_sum == target: 
        # result gotten. Return early
        res.append(right + 1)
        return res
    elif sub_sum < target:
        # only move right when sub array sum is less than target
        right += 1

        # assert that right pointer is within array bounds before accessing value
        if right >= len(arr): return res
        sub_sum += arr[right]
        # when subarray sum is greater than target, don't stop expanding the window. A negative-positive combo might exist ahead
        # for example -1,-1, 5, -1 and target 2
        right += 1

        # end of array. We are now certain that no combo exists for the subarray window
        # shrink window: 
        # 1. by deducting the value at left pointer and move left pointer forward
        if right == len(arr) - 1:
            sub_sum -= arr[left]
            left += 1

            # 2. and move right pointer to just a step ahead of left pointer
            right = left + 1

            # with a new window, we need to recalculate window sum afresh and discard old sum
            sub_sum = arr[left] + arr[right]
        if right > len(arr): return res
return res

Please correct the time complexity explanation for the brute force approach - the complexity of:

N subarrays with size 1, N-1 subarrays with size 2 .. and 1 subarray with size N

is not O(N^2), but O(N^3) [1]. Unless you introduce some optimization (e.g. computing each subarray based on the previous + new element) that was not mentioned.

[1] source:

Can someone explain why we are returning i + 1 index and not i as the starting index for the subarray sum?

prefix_sums[cur_sum] = i + 1

This article says we should use a prefix sum to resolve the problem, which is fine. However, what we are asked to get (the longest subarray that sums X number) is almost the same as in this other problem: Sliding Window - Longest - Two Pointers / Sliding Window. The only significant difference I see is that in this problem the input has negative numbers whereas the other does not.

So why are we using different algorithms for these 2 problems? Is it because of the negative numbers in the input or because of something else I’m missing?