SUBARRAY SUM EQUALS K | LEETCODE 560 | PYTHON SOLUTION

Channel Discord Community: / discord
Problem Link: leetcode.com/problems/subarra...
Today we are solving a god awful problem that is an absolute chore to explain: Subarray Sums Equals K (Leetcode 560). The code for this problem is very straightforward but the explanation is so difficult as you'll see... even I'm struggling to explain and that's helped by the terrible examples given for this problem.
TIMESTAMPS
00:00 Intro
00:08 Question Prompt
00:21 Basic Example
01:39 Solution Intuition
07:28 Coding
12:24 Explaining prefix_dict[0] = 1
14:40 Time/Space Complexity
15:30 Outro

[@ajvercueil8111]

"prefix_dict[0] = 1" basically replaces "if prefix_sum == k: counter += 1" in our loop

[@massimomonticelli6010]

Using a defaultdict(int) makes the check if the key is in the dictionary unnecessary (line 15), as the defaultdict automatically initializes the value to 0 if the key does not exist.

[@dnm9931]

What a horrible question! Thanks so much for all you do , you are appreciated !

[@codewithmarish]

At first glance, I couldn't catch up but If we observe carefully it is similar to the two-sum problem and we need to know which point we just need to see if any of the pre-calculated prefixes match with current_sum - k
Thanks for your explanation It helped a lot.

[@YT.Nikolay]

Ah wow!!! Never knew about this feature, nice to know :)

[@crackfaang]

You've been along for so long you've more than earned the right to just request the content you want to see. Just DM me on discord

[@koreandude]

thanks for the awesome explanation!
had a question, in the example, shouldn't it be prefixes = [1, 3, 9, 4], if nums = [1, 2, 7, -3]?

[@tsimbaland2905]

prefix sum says that each next number in prefix sum array should be the sum of the previous ones and the number itself.
So, if prefixes = [1, 3, 9, 4], nums = [1, 2, 6, -5]
if nums = [1, 2, 7, -3], prefixes = [1, 3, 10, 7] ( 1, 1+2, 1+2+7, 1+2+7-3)

[@3rd_iimpact]

It's nice to know that I'm not the only who has a hard time explaining this one, lol.

[@crackfaang]

Welcome as a channel member mate!

[@tanvirahmed7993]

sumI - k = sumJ, where I < J, was the key

[@dmytryemery]

haha, I did this question sooo many times trying to understand prefix sum questions.
I was able to code it up from memory, but was totally shook if I got asked it in an interview.. because explaining my thought process :D
Seriously this question is hard af. Screw the medium rating.

[@crackfaang]

Yea it's just one of those where you really need a pen and paper to hammer in the logic. Once it clicks you can understand the solution to all these types of questions but I agree it's really hard the first time seeing it.

[@skh9749]

I think if sum(i) - sum(j) = 0 that means sum(i+1 to j) including element at j equals 0, right? In the example prefix sum of [1,2,3,-3] is [1,3,6,3] so sum(0..1)-sum(0..3) = 0 so sum(2..3) = 0 i=1, j=3 sum(i+1..j)

[@HarbiDr]

Emotional Damage @ 5m 31s

[@ansupriyadarshi1456]

You could have made that 100X clearer.

[@crackfaang]

Yea this is the shit explanation. My better one for the divisible/equals K problems is in the video for Subarray Sums Divisible By K. It's one of those where if you know how it works it all makes sense but explaining it is harder than learning it lol