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?