Subarray Sum Equals K - Prefix Sums - Leetcode 560 - Python

0:00 - Read the problem
2:27 - Drawing Explanation
13:11 - Coding Explanation

leetcode 560

#prefix #sum #python
Disclosure: Some of the links above may be affiliate links, from which I may earn a small commission.

[suvajitchakrabarty]

If you are having difficulty understanding this or wrapping your head around the solution, maybe this might be a good way to think about it. The question asks how many subarray sum equals to k. For a subarray to sum to k, you need a subarray, as in a part of the array from index 'a' to index 'b' to have a sum equal to k. But when we reach any index 'b', we obviously do not know, if there was a subarray from index 'a' to index 'b' equal to k. However we do have the sums from 0 to index 'a' in our hash map, because we have been storing all sums starting from index '0' to every single index till now, and the count of them as the value of the key. Now obviously sum_0_to_a + sum_a_to_b = total sum so far (curSum). If we go to the original ask, which is we need a prefix that is sum_a_to_b to be equal to k. For that to hold true, replace sum_a_to_b with 'k'. Hence, sum_0_to_a + k = curSum. Hence curSum - k = sum_0_to_a. And then since we have been storing all possible values of sum_0_to_a so far in the hashmap, curSum - k must exist in the hashmap as a key, and we can simply add the value from the hashmap to add number of prefixes from 0 to any index which equalled to curSum - k .

[kimstuart]

You know I remember first learning CompSci, I thought the specific algorithm concepts (BFS, DFS, Dijkstra, etc.) were the hard ones to learn. Now that I am more experiences, I realize that the what I thought then were 'basic' data structures, i.e. arrays, strings, etc. are actually the harder ones to make sure you understand because those concepts has many dedicated algorithms to them, such as Kadane, prefix/suffix array, KMP etc. that you need to know to truly understand that data structure. So while I glossed over arrays because I knew their functions, I am now revisiting to make sure I understand the algorithms embedded in them. Learning truly never does stop!

[Question]

I like your attempt to explain it, even though I don't fully understand it. I appreciate it.

[ObaidullahGhawsi]

Thanks, NeetCode for these solutions and explanations, It would be really helpful to make a video about general techniques that you use to solve these problems... Because we wan to know how to approcah these kinds of problems by ourselves. Thanks again.

[apoorvwatsky]

1:55 I needed to hear that, I wanted to know why sliding window won't guarantee correct answer for these constraints. That cleared it up.

[josembass]

Great explanation.

How are we supposed to come up with a solution like this in 30m without having seen it before!

[CliffordFajardo]

Initially I thought it was a sliding window problem, Trying to wrap my head around this ...patience, time...ahhh. Thanks for the video!

[scottloewke]

Good explanation and, fortunately, the omission of the [key = 2, count = 1] map entry did not affect the result. However, it would be good if NeetCode could add text at that part in the video to make it clear what happened.

[mangalegends]

I'm still trying to wrap my head around this

EDIT: Came back a few weeks later and it makes 100% sense to me now

[timzhang]

Well explained, and it takes effort to make a video as good as this. Thank you!

[darkwhite]

08:21 - i have no idea how we are supposed to figure out during the coding interview that (0, 1) has to be added into the hashmap by default. How is anyone solving this without memorizing during interviews? May be i'm dumb to not understand this even though the instructor is explaining it. Please help me understand the intution behind adding (0, 1) in hashmap by default.

[tempregex]

i appreciated you explaining this. But, it would have been more helpful(esp to people like me) where you would have taken the time to explain more about the use of HashMap for maintaining prefixSum -> Count to me it felt like the explanation went "too fast" as soon as you discussed the brute force solution.But, in any case a great attempt indeed.

[Retrosenescent]

You explained it so perfectly that I didn't even need to see the code to be able to code it myself :) thank you!!

[arunraman]

A slightly cleaner solution using a defaultdict

class Solution:
def subarraySum(self, nums: List[int], k: int) -> int:
prefixSums = defaultdict(int, { 0 : 1 })
curSum = 0
res = 0

for n in nums:
curSum += n
res += prefixSums[curSum - k]
prefixSums[curSum] += 1

return res

[XMaverick]

00:40 The brute force approach is O(n^3), not O(n^2). There are ~n^2 subarrays but summing a subarray is O(n).

[Adam-tzgk]

This is by far the best explanation in the web for this problem, thank you so much NeetCode!

[unwarysagew]

This is a way better explanation than leetcode premium’s explanation thank you!

[uzzwalpreetkaur]

I understood this explanation! Thanks!! I was trying with sliding window technique first and getting the wrong answer until I realised that we can have negative numbers. This is indeed is a neat.

[edwardteach]

Another way to think about why we would set our key value to {0:1} instead of memorizing, is to think what if that single element, itself is the target.

For example:
input = [1, 1, 4], k = 4
occur = { 0: 1 }

By just eyeballing, you'll see the output is 1, since the last element is a 4. When we iterate through the input, we'll do input[2] - k (4 - 4) = 0. Do we have a 0 in our hashmap/dictionary? Yes we do, it's value is 1.

[almasabdrazak]

so what you are saying is we have a map that shows how many ways we can come up with given sum so for sum 0 we can come up with 2 sequences, but these sequences have to be contiguous, how to prove that 0 has 2 only if we pop up contiguous elements from current sum ?