Continuous Subarray Sum - Leetcode 523 - Python

0:00 - Read the problem
1:15 - Intuition
6:30 - Drawing Explanation
12:08 - Coding Explanation

leetcode 523

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

[mdazharuddin]

We add {0 : -1} in dict not to handle case where 1st element is divisible by k. We add it to handle case where subarray starting from 0 is divisible by k.

For example when k = 6 and nums = [1, 2, 3, 4] and we don't initialize 0, we will get False.

[dantesmith]

I wrestled with this one for a couple hours... I was trying to store the prefix sum, not the remainder, and I was having a tough time making that work. Storing the remainders is a great idea, and made the code much more concise! Thanks!

[hanklin]

Is it possible to think of hashing the remainder in an actual interview? What 'intuition' could anyone even come up with it in the first place?

[adam-zytb]

wouldn't space complexity be O(k) since you are storing at most k entries in the hashmap? i.e. if k = 6 you are storing at most 6 entries since the remainder would never be more than 5 (+1 more for the 0 edge case)

[ObtecularPk]

Again, how is someone able to come up with a solution like this in a time limit interview? This is the question that needs answering next video or something

[mirceskiandrej]

This is not a medium question. It is hard, borderline extreme.
If you see the solution, it becomes easy since it's memorable, but you cannot average easy and hard to get a medium question 😃

[redblacktech]

awesome vid! i'd like to add that the optimized solution is like two-sum in the sense that we're caching complementary values. once you see it this way it becomes intuitive, however, there's no way in hell the average person is going to figure that out without tons of practice doing leetcode questions specifically 🙃

i'd ALSO like to add a one line intuition for the key point of this video:
if we see two numbers that when % by k have the same remainder, then those numbers are either k away from each other (or multiple of k away from each other) - and this is exactly what the problem is asking us to find

[avanishgvyas]

Nice explanation. Impossible to come up with this solution in 25 minutes while under stress in an interview.

[AlexN]

the easier-to-come-up-with solution can still work:
1. calculate prefix array and store in a map (sum->leftmost index where found)
2. r = 0; r < size; r++
3. calculate the current rmdr = sum%k
4. if we could find a sub-array on the left with sum=rmdr, we could remove that subarray from [0:r] and sum%k would be 0
5. look for rmdr in the map. If found && index < r - we have found the sub-array to remove

[finchshi]

bro you are my favorite leetcode channel

[ivankok]

Nice solution and explanation. I was struggling to find a faster solution, but this duplicate remainder approach is very creative!

[Dumbastic]

Thank you for the clear explanation, I saw the solution before, but I couldn't get behind why it was neccessary to have a duplicated modulo result value in the array. You were able to explain it in a simple manner, appreciate it a lot! Keep up the good work! :)

[rongrongmiao]

I hate math questions. To solve this problem all we need to know is that (a-b)%c = ((a%c) - (b%c)) % c. so to get a-b mod c = 0, just need to have this: a mod c = b mod c

[CreeperFace]

great vid! No idea how u come out with these solutions but they make perfect sense

[aadityakiran_s]

Got asked a harder variation of this in a Google interview. No real hint was also provided by the interviewer. I suppose luck is also a factor. If you've seen the problem before or if you're able to fit whatever problem, you get into the pattern that you've seen before.

[Ryan-gh]

Hey guys also don't forget this video is missing a key detail:
look into why we use elif i - remainder[r] > 1 instead of >=. It ties to the {0:-1}
and a edge case such as [6, 1, 2], k = 6 -> should false but if we do >= return True

[vadimkokielov]

first i want to make sure you, but also anyone else knows. I am not writing suggestions because I don't need your videos and the help they give. I need them a lot. I am intensively preparing for an interview. Whatever I write is anything I discover on top of your solutions.

That said...You can spare the map and use a hash set. Just keep it trailing behind by one index, so you don't get any invalid values.

I am sure you know this solution, and if you decided not to explain it because the mind xxxx of the problem itself is pain enough, then I absolutely agree with you. It's worth pointing out, however.

[priyankachoudhary]

Amazing explanation! I don't think I would have been ever able to understand this question without your elegant and detailed explanation about what works and what doesn't work and why it doesn't work.

[shadowthehedgehog]

Damn this solution is crazy.. i don’t think I would even think of this

[algosavage]

just best. I'm watching you for about a year and just wanna say that u'r the best! Thanks for ur job!