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?
What about the case where you run into the same complement again? Doesn’t that mess up the count?