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
-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.

``````prefix_sums[cur_sum] = i + 1