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

-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(left)
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]
else:
# 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: https://www.youtube.com/watch?v=dUs5-Ak4WSw

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?