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.
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)
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 😃
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
i am thinking the same..in most of these problems..I guess there are three ways: a) you should know the problem beforehand and solve it..so it would be relatively easy to repeat during interview..b) you get plenty of help from the interviewer and you kinda solve it with bugs or/and pseudocode..c) you have spend your life with LC and you solve it in 15' seeing first time.. I dont see myself even close to option c and i guess i have to practice 10 times more..but i would be curious if someone who has passed the interview can tell
@@easynow6599 I had an interview with a big tech company like last week. I was able to solve roughly 2 problems that I had never seen before that I would categorize as leetcode easy's. They had edge cases that took time and killed like 35 min. The other two however one was hard and the other was either hard or medium. I had no idea how to solve them. I was able to get some work in but couldnt pass all the cases. I later looked them up for hours and was able to find 1 similar but not entirely the same. I spent like 2 hours trying to understand and solve the problem I found. There is no way someone can solve these in 15 minutes.
@@josecabrera7947 i dont know man..this leetcode looks like a BS system.. but discussing about that i think it's the optimal way to filter people..with a lot of false negatives (a lot of good people stay out because a problem was too hard to solve) and a some false positives (people that grind LC as hell, but in reality they dont know much stuff).. Anyway..i wish you good luck!
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
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!
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
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
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.
yeah you can def do it with a set and a prev value where prev = sum % k. Personally I find the hashmap solution a little easier to understand and remember.
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! :)
Omg the the solution is so damn cool ! I tried out the same lines you talked about in the beginning but it led me nowhere so i was feeling pretty dumdum :p Thank you for your clear explanation as always, it really helps :)
Your original trains of thought about the 2sum problem as well as a prefix sum approach were also doable, if you had dived deeper into them and made minor modifications. Here is a 2sum-like approach to solving this problem in one pass: class Solution: def checkSubarraySum(self, nums: List[int], k: int) -> bool: seen = set() prv = cur = 0 for x in nums: cur, prv = (cur + x) % k, cur if cur in seen: return True seen.add(prv) return False
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.
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.
The thought process that helped me get to the solution was by thinking of the problem Largest Subarray with sum 0, as we use hashmap to store the sum with index.
The time complexity of the brute force solution (by summing up the sub-arrays in sliding windows with cumulative sum) seems to be O(n!), which is worse than O(n^2).
used this to solve 974. made a few changes. def checksumarray_k(nums, k): remainder={0:[-1]} total=0 count=0 for idx, element in enumerate(nums): total+=element r=total%k if r not in remainder: remainder[r]=[idx] else: count+=len(remainder[r]) remainder[r].append(idx) return count
I managed to do this on my own with prefix sum approach. My approach is different though and is more than O(n). Following is the code. bool checkSubarraySum(vector& nums, int k) { int sum = 0; unordered_map hash; for (int i = 0; i < nums.size(); i++) { sum += nums[i]; if (!i) { hash[sum] = i; continue; } if (sum % k == 0) return true; int j = 0; while (k * j < sum) { int rem = sum - k * j; if (hash.count(rem) && i - hash[rem] >= 2) { return true; } j++; } if (!hash.count(sum)) hash[sum] = i; } return false; }
Thank you so so so so soooo much for this. I was on the right track with modulo and thinking of a sliding window, but was missing the last piece with prefix sum.
Java Solution: class Solution { public boolean checkSubarraySum(int[] nums, int k) { HashMap map = new HashMap(); // To store int prefixSum = 0; map.put(0, -1);
for (int i = 0; i < nums.length; i++) { prefixSum += nums[i]; int remainder = k == 0 ? prefixSum : prefixSum % k;
if (map.containsKey(remainder)) { int length = i - map.get(remainder); if (length >= 2) { return true; } } else { map.put(remainder, i); } }
Can someone tell me whats this , what is x and n are that values of array " An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k "
Another way to handle the edge case when prefix sum will itself be a multiple of k, arr = [24,0,2] k = 6, [24,0] subarray sum is a multiple of 6. if(prefSum % k == 0 && idx > 0) return true;
hi @neetcode i Try to solve it Using Sliding Window It passes Most of the Test Csaes but if array consist of 0 then its failing 93/99 test cases are passed but this one if failing nums = [1,3,6,0,9,6,9]. , k = 7 output : True if len(nums) < 2: return False currSum = 0 totalSum =nums[0] l= 0 for r in range(1, len(nums)): currSum = nums[l]+ nums[r] totalSum +=nums[r] if currSum % k == 0 or totalSum % k == 0 : return True l+=1 if totalSum % k == 0: return True return False could you please See It Please
Java solution for the same public boolean checkSubarraySum(int[] nums, int k) { HashMap map = new HashMap (); int sum = 0; map.put(0, -1); boolean found = false; int n = nums.length; for(int i=0; i< n; i++) { sum = sum + nums[i]; int hash = sum % k; if(map.containsKey(hash)) { int diff = i - map.get(hash); if(diff>=2) { found = true; break; } } else { map.put(hash, i); } } return found; }
Python is so easy for OA. Sadly, I'm more comfortable writing in Java. Imagine "remainder = { 0, -1 }". Java would be first import Map and hashMap, then Map remainder = new HashMap(); map.put(0, -1);. So sad. So so sad!
why you need to add 0, -1 TC; arr= [2,4,1] k = 2 if you not add 0,-1 in map it return false at index 1 ==> 6 % 2 == 0 index - map.get(0) >=2 ==> return true
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.
Thanks! I watched the video and could not understand why {0:-1} and you answered my question. Very appreciate!
Great addition to the video! Thanks for the clarification.
Yep. Also a way to get rid of that is to have `if (remainder == 0 && i > 0) return true` in the for loop
yeah, this makes sense
you Can Just Add this Condition
if sum%k==0 and i>=1:
return True
Continuous Subarray Sum of PAIN
yeah, fuck this problem.
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?
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)
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 😃
ikr. for days ive been trying LOL... really out of the box thinking to come up with this
100% true!
I was asked this question for a new grad job at a small company fml
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
i am thinking the same..in most of these problems..I guess there are three ways: a) you should know the problem beforehand and solve it..so it would be relatively easy to repeat during interview..b) you get plenty of help from the interviewer and you kinda solve it with bugs or/and pseudocode..c) you have spend your life with LC and you solve it in 15' seeing first time..
I dont see myself even close to option c and i guess i have to practice 10 times more..but i would be curious if someone who has passed the interview can tell
Step 1: Solve it before the interview
Step 2: Solve it during the interview and pretend you've never seen it
I second that... looks interview is pure luck...
@@easynow6599 I had an interview with a big tech company like last week. I was able to solve roughly 2 problems that I had never seen before that I would categorize as leetcode easy's. They had edge cases that took time and killed like 35 min. The other two however one was hard and the other was either hard or medium. I had no idea how to solve them. I was able to get some work in but couldnt pass all the cases. I later looked them up for hours and was able to find 1 similar but not entirely the same. I spent like 2 hours trying to understand and solve the problem I found. There is no way someone can solve these in 15 minutes.
@@josecabrera7947 i dont know man..this leetcode looks like a BS system.. but discussing about that i think it's the optimal way to filter people..with a lot of false negatives (a lot of good people stay out because a problem was too hard to solve) and a some false positives (people that grind LC as hell, but in reality they dont know much stuff)..
Anyway..i wish you good luck!
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
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!
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
Nice solution and explanation. I was struggling to find a faster solution, but this duplicate remainder approach is very creative!
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
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.
yeah you can def do it with a set and a prev value where prev = sum % k. Personally I find the hashmap solution a little easier to understand and remember.
bro you are my favorite leetcode channel
Appreciate that :)
I feel you need to be good at math to crack this one on your own.
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! :)
I am a continuous sub array
great vid! No idea how u come out with these solutions but they make perfect sense
Omg the the solution is so damn cool ! I tried out the same lines you talked about in the beginning but it led me nowhere so i was feeling pretty dumdum :p Thank you for your clear explanation as always, it really helps :)
Nice explanation. Impossible to come up with this solution in 25 minutes while under stress in an interview.
Your original trains of thought about the 2sum problem as well as a prefix sum approach were also doable, if you had dived deeper into them and made minor modifications. Here is a 2sum-like approach to solving this problem in one pass:
class Solution:
def checkSubarraySum(self, nums: List[int], k: int) -> bool:
seen = set()
prv = cur = 0
for x in nums:
cur, prv = (cur + x) % k, cur
if cur in seen:
return True
seen.add(prv)
return False
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.
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.
I was asked the same question in my Accolite Digital interview, glad I had already solved it before otherwise I would have been doomed!!!!
just best. I'm watching you for about a year and just wanna say that u'r the best! Thanks for ur job!
Only explanation that my brain understood. Thank you Neetcode.
Damn this solution is crazy.. i don’t think I would even think of this
The thought process that helped me get to the solution was by thinking of the problem Largest Subarray with sum 0, as we use hashmap to store the sum with index.
Awesome explanation.... for an insane problem. Great work !!!!!
Very elegant explanation. Thanks a lot. Can you please do Leetcode 2060 as well?
The time complexity of the brute force solution (by summing up the sub-arrays in sliding windows with cumulative sum) seems to be O(n!), which is worse than O(n^2).
Yeah, after coming to prefix sums, I couldnt think about this so tricky either you see the math or you dont
Amazing Explanation Bro. Your explanation videos made my DSA skills far better.
There is a step after calculating r you can also check if r == 0 return True
used this to solve 974. made a few changes.
def checksumarray_k(nums, k):
remainder={0:[-1]}
total=0
count=0
for idx, element in enumerate(nums):
total+=element
r=total%k
if r not in remainder:
remainder[r]=[idx]
else:
count+=len(remainder[r])
remainder[r].append(idx)
return count
This solution is just awesome !!! Thanks @NeetCode .
So key point here is if prefixsum%k=r and (prefixsum+x1+x2+•••••+xn)%k=r then undoubtedly x1+x2+•••••+xn is multiple of k
I managed to do this on my own with prefix sum approach. My approach is different though and is more than O(n). Following is the code.
bool checkSubarraySum(vector& nums, int k) {
int sum = 0;
unordered_map hash;
for (int i = 0; i < nums.size(); i++) {
sum += nums[i];
if (!i) {
hash[sum] = i;
continue;
}
if (sum % k == 0) return true;
int j = 0;
while (k * j < sum) {
int rem = sum - k * j;
if (hash.count(rem) && i - hash[rem] >= 2) {
return true;
}
j++;
}
if (!hash.count(sum)) hash[sum] = i;
}
return false;
}
Mind blown. Who would've come up with that trick from the get go haha?
Amazing explanation as always
Thank you so so so so soooo much for this. I was on the right track with modulo and thinking of a sliding window, but was missing the last piece with prefix sum.
only leetcoder who makes sense tbh. Well done.
Yep, it's hard to come up with the part 'i-remainder[r] > 1' by my own. It's great that we leave in the era of streaming to gain best practices
Java Solution:
class Solution {
public boolean checkSubarraySum(int[] nums, int k) {
HashMap map = new HashMap(); // To store
int prefixSum = 0;
map.put(0, -1);
for (int i = 0; i < nums.length; i++) {
prefixSum += nums[i];
int remainder = k == 0 ? prefixSum : prefixSum % k;
if (map.containsKey(remainder)) {
int length = i - map.get(remainder);
if (length >= 2) {
return true;
}
} else {
map.put(remainder, i);
}
}
return false;
}
}
Definitely Like Your Work Bro......Your Explanation Rocks!!!!
I think because of this approach this should have been marked as hard problem.
Hey neet, this is neat!
2 sum or sliding windows. Your false ideas were exactly what I was trying to do.
Hey, I'm new to this channel. I loved how you explained it so easily! Thanks :)
What if we wanted to know where or wich list entries give us this multiple?
Can someone tell me whats this , what is x and n are that values of array " An integer x is a multiple of k if there exists an integer n such that x = n * k. 0 is always a multiple of k "
Amazing intuition
You got a new subscriber!!
Does any one know why when we encounter a remainder that already exists in the hash map, there exists a sum that is %k ?
because if the remainder wraps around, we know that it changed by k
I have been watching your videos and May be it helped I don’t know but I had the same idea to solve the problem before seeing the solution 😃
Another way to handle the edge case when prefix sum will itself be a multiple of k, arr = [24,0,2] k = 6, [24,0] subarray sum is a multiple of 6. if(prefSum % k == 0 && idx > 0) return true;
Very well explained !
thank you neet
Can you do 410. Split Array Largest Sum? Thank you!!
great explanation bro💗
You made it very easy for me 🔥🔥💯
thanks, great intution.
Could you please make videos on systems designs as well, if possible?
me as a day of life an unemployed dude :(
Well done on this video
hi @neetcode
i Try to solve it Using Sliding Window It passes Most of the Test Csaes but if array consist of 0 then its failing 93/99 test cases are passed
but this one if failing
nums = [1,3,6,0,9,6,9]. , k = 7
output : True
if len(nums) < 2:
return False
currSum = 0
totalSum =nums[0]
l= 0
for r in range(1, len(nums)):
currSum = nums[l]+ nums[r]
totalSum +=nums[r]
if currSum % k == 0 or totalSum % k == 0 :
return True
l+=1
if totalSum % k == 0:
return True
return False
could you please See It Please
Could it be solved using Brute force method? If solved, then how?
Java solution for the same
public boolean checkSubarraySum(int[] nums, int k) {
HashMap map = new HashMap ();
int sum = 0;
map.put(0, -1);
boolean found = false;
int n = nums.length;
for(int i=0; i< n; i++) {
sum = sum + nums[i];
int hash = sum % k;
if(map.containsKey(hash)) {
int diff = i - map.get(hash);
if(diff>=2) {
found = true;
break;
}
} else {
map.put(hash, i);
}
}
return found;
}
Thanks !
thanks
great solution
AMAZING IDEA 😍🌹
Python is so easy for OA. Sadly, I'm more comfortable writing in Java. Imagine "remainder = { 0, -1 }". Java would be first import Map and hashMap, then Map remainder = new HashMap(); map.put(0, -1);. So sad. So so sad!
i did not try it but it looks like this could be solved with segment trees
You are so smart!! I would like to elect you president.
this should have been a hard problem.
this is insane
This problem is mainly optimization.
Is there a real life use case for an algorithm for this?
doubt it
OMG, so tricky!!!!!
Great concept but really this approach is difficult to come up with.
I was recently asked this question in an interview and I was solving it through a two-pointer approach but I failed to optimize and got rejected 😥
which company??
[5,0,0,0]
3
Expected output : True
How can it possible ??
0 and 0 are a continuous subarray hence making 0+0 = 0%k expects to fulfil the condition. hence returns true
Still unable to understand how it has checked all subarrays' sum
Dope
i laughed when i saw the solution its sooooooo clever
How much IQ is required here to come up with the solution on the first look?
oh god
Ninja level
yo, neetcode, bro, your solution doesn't work
Great yaar i was missing some cases ... thanks
why you need to add 0, -1
TC; arr= [2,4,1] k = 2
if you not add 0,-1 in map it return false
at index 1 ==> 6 % 2 == 0
index - map.get(0) >=2 ==> return true
Thanks!
Thanks!
Thank you so much!!