What sets you apart from the other youtubers is the fact that you don't just explain the solution. You also explain why other methods don't work? why only this method works? and how exactly do we come up with this solution? This video was an amazing explanation . Thank you for that.
I started leeting in the new UI and accidentally switched to the OG UI once through some keyboard shortcut. I was terrified of the old UI. Glad I was able to switch back to the new one. It just depends on what you're used to.
I immediately thought of a sliding window and tried that, thanks for explaining why that wouldn't work. That type of explanation, mentioning why a particular solution doesn't work in this case is really really helpful.
Very interesting approach. This is the TDLR for the comment section: 1. Maintain a count variable as you iterate through array. For each 0 subtract count by 1 and add by 1 for each 1. 2. Maintain a hash map in which you store the leftmost index for each count value and initialize it with 0: -1 3. As you iterate through the array if the current count value already exists in the hash map, update the size with curr_idx - map[curr_count] if that value is greater than the greatest size so far
I would have died trying to solve this problem using sliding window if you hadn't explained why we can't use sliding window here. Thanks a lot Neetcode.
this particular problem sets apart people that has spent a huge amount of time on leetcode and somehow got the intuition for this, from people who may well be great coders but don't grind leetcode
Just find the prefixSum arr, add 1 if 1 or -1 if 0 or vice versa, use hashMap to compare prev values but don't store when the sum repeats otherwise it will overwrite, check the sum=0 case also
Great solution as usual. 🔥 But, hope the following might make it less complex: In simple terms, in the array, if you see 1 -> preSum - 1 0 -> preSum + 1 Then, you just have to check two cases - 1. If the preSum is 0 (equal number of 1s and 0s till that index) -> update result index 2. If the preSum already exists -> check the difference - NOTE: Should not update the hashmap (we only want the first seen preSum to stay to maximise the result) If not both, we are seeing this preSum for the first time -> Add it to hashmap
Code for better understanding: def findMaxLength(self, nums: List[int]) -> int: preSum = 0 ans = 0 d = {}
for i in range(len(nums)): #calculating preSum if nums[i] == 0: preSum += 1 else: preSum -= 1
#if the preSum is zero -> equal number of 1s ansd 0s if preSum == 0: ans = max(ans, i + 1)
#the other case is that we have seen it already elif preSum in d: ans = max(ans, i - d[preSum]) #seeing this preSum for the first time else: d[preSum] = i return ans
@NeetCodeIO, you can shift the sliding window. Suppose we have array = [1, 1, 1, 0, 0, 0]. As the the maximum length of the array is 6. We can consider the length of the array as a limit. If the sliding window has 3 one's and 2 zero's, and the length of the array is 6 then we can definitely shift our right side by 1. But if we have 4 one' and 1 zero's, the shifting the right side by does not make sense. So we will shift the left side of the window by 1.
I am in the final grade in Russian Highschool, and I actually saw this problem preparing for my informatics exam (it was not with 0s and 1s, it was the problem to find the longest window that has the largest sum that meets all the requirements, but the idea was also about to keep all the prefixes), it was the last problem in the previous year's exam. I hope I will not get something like this, because I wont be able to solve it under the pressure, haha
Yes, please show me another solution where you use -1 and 1. I would really like to see him, in general, this is a very difficult task for me. Thank you for the video!
Honestly I didn't think that much but I was able to solve the question :p. My thought process was "how about I get the largest array with sum = 0 and how to do that? consider every 0 as a -1"
it was great explanation, I do understand the solution after watching your video. But how coming up with such solution is not intuitive for me, could you please help with that in any way?
n! is equal to n * n-1 * n-2 * .... * 2 * 1, while the solution at 0:46 is n + n-1 + n-2 + .... + 2 + 1 which is (n(n+1))/2 which we simplify to O(n^2)
Hey @NeetCodeIO, won't it be a better solution to use double pointers one at index 0 (s) and another at index n -1 (e), and increment or decrement s and e depending on the number of 1es. if sum(array[s:e]) * 2 > (e - s + 1), s++ if array[s] == 1 or e-- if array[e] == 1 else if sum(array[s:e]) * 2 < (e - s + 1) , s++ if array[s] == 0 or e-- if array[e] == 0 else return array[s:e]. let me know what you think.
What if we count all zeroes and ones first time and will use sliding window by decreasing it from right and left. For example, we have 3 zeros and 5 ones. We will decrease the side where we have ones or zeros if we don't have ones from each side and each time update(decrease) zeros and ones values. Will it work?
Include comments! Sometimes the hardest part is intuiting the solution, so seeing how you got from Sliding Window to this Prefix Sum is interesting. Glad to have your videos & roadmap as I prep for interviews. Thx a bunch.
am i the only one who wasn't able to pass all the testcases with this? here's my code, just in case someone can help point out my mistake class Solution: def findMaxLength(self, nums: List[int]) -> int: zeros, ones = 0, 0 diff_index = {} res = 0 for i, n in enumerate(nums): if i == 0: zeros += 1 else: ones += 1 if ones - zeros not in diff_index: diff_index[ones - zeros] = i
if ones == zeros: res = ones + zeros else: idx = diff_index[ones - zeros] res = max(res, i - idx) return res
I guess you've already figured it out, but just in case you haven't, your code should be: if n == 0: zeroes += 1 else: ones += 1 Because you need to be checking if each element of the array is equal to zero, not if the index is zero.
What sets you apart from the other youtubers is the fact that you don't just explain the solution. You also explain why other methods don't work? why only this method works? and how exactly do we come up with this solution?
This video was an amazing explanation . Thank you for that.
I would never think of this without seeing it before.
I think the idea is you are aware of the solution. Whether you came up with it on your own or not is not the point.
What does everyone think of the new leetcode UI? Kinda annoying that they don't let you switch back to the old one anymore
I started leeting in the new UI and accidentally switched to the OG UI once through some keyboard shortcut. I was terrified of the old UI. Glad I was able to switch back to the new one. It just depends on what you're used to.
ya, it's better to be able to switch between them
I immediately thought of a sliding window and tried that, thanks for explaining why that wouldn't work. That type of explanation, mentioning why a particular solution doesn't work in this case is really really helpful.
I just got into LeetCoding recently so I'm cool with it. If I could try the old UI I would.
Same here
I signed my Apple summer internship offer letter yesterday, thanks a lot for all your help. I hope you continue doing what you do the best
woah. the dream
Very interesting approach. This is the TDLR for the comment section:
1. Maintain a count variable as you iterate through array. For each 0 subtract count by 1 and add by 1 for each 1.
2. Maintain a hash map in which you store the leftmost index for each count value and initialize it with 0: -1
3. As you iterate through the array if the current count value already exists in the hash map, update the size with curr_idx - map[curr_count] if that value is greater than the greatest size so far
I would have died trying to solve this problem using sliding window if you hadn't explained why we can't use sliding window here. Thanks a lot Neetcode.
What a genuine mind, what a talent to explain far-not intuitive concepts in a clear, easy to grasp manner!!
How have you not won awards for your work. Been using your solutions for years now, I love you neetcode🌸
Thank you so much 🙏
Hi Navdeep, thank you for your solution! It will be extremely helpful if you include the brainstorming notes too in the future videos. Thanks!
These problems are beautiful and set apart top-level coders from the rest. Hope one day to be able to solve this kind of problems myself.
this particular problem sets apart people that has spent a huge amount of time on leetcode and somehow got the intuition for this, from people who may well be great coders but don't grind leetcode
@@llorensbf That's also true, i would not give this problem at an interview as it doesn't show much technique.
Just find the prefixSum arr, add 1 if 1 or -1 if 0 or vice versa, use hashMap to compare prev values but don't store when the sum repeats otherwise it will overwrite, check the sum=0 case also
leetcode- Replace Question Marks in String to Minimize Its Value. Solve this question in python in easiest way.
Great solution as usual. 🔥
But, hope the following might make it less complex:
In simple terms, in the array, if you see
1 -> preSum - 1
0 -> preSum + 1
Then, you just have to check two cases -
1. If the preSum is 0 (equal number of 1s and 0s till that index) -> update result index
2. If the preSum already exists -> check the difference - NOTE: Should not update the hashmap (we only want the first seen preSum to stay to maximise the result)
If not both, we are seeing this preSum for the first time -> Add it to hashmap
Code for better understanding:
def findMaxLength(self, nums: List[int]) -> int:
preSum = 0
ans = 0
d = {}
for i in range(len(nums)):
#calculating preSum
if nums[i] == 0:
preSum += 1
else:
preSum -= 1
#if the preSum is zero -> equal number of 1s ansd 0s
if preSum == 0:
ans = max(ans, i + 1)
#the other case is that we have seen it already
elif preSum in d:
ans = max(ans, i - d[preSum])
#seeing this preSum for the first time
else:
d[preSum] = i
return ans
Perfect even i was thinking the same. Simple and easy to understand
How are you supposed to know this without seeing it before :(
The comments are a great addition, Navdeep Paji
This is a very smart solution, I came up with a prefix sum solution which was basically convoluted O(N^2) solution
Congrats on 100k 🎊
It's a Prefix sum problem
Congrats on 100k!
I was struggling with visualising the solutions, Thank for such easy explanation.
@NeetCodeIO, you can shift the sliding window.
Suppose we have array = [1, 1, 1, 0, 0, 0].
As the the maximum length of the array is 6. We can consider the length of the array as a limit. If the sliding window has 3 one's and 2 zero's, and the length of the array is 6 then we can definitely shift our right side by 1. But if we have 4 one' and 1 zero's, the shifting the right side by does not make sense. So we will shift the left side of the window by 1.
Finally an explanation I understood perfectly. Thanks!
bro thank you for explaining why sliding window doesnt work I love u
I am in the final grade in Russian Highschool, and I actually saw this problem preparing for my informatics exam (it was not with 0s and 1s, it was the problem to find the longest window that has the largest sum that meets all the requirements, but the idea was also about to keep all the prefixes), it was the last problem in the previous year's exam. I hope I will not get something like this, because I wont be able to solve it under the pressure, haha
Yes, please show me another solution where you use -1 and 1. I would really like to see him, in general, this is a very difficult task for me. Thank you for the video!
1 ) change all 0's to -1's
2 ) now the question changes to finding the longest length subarray whose sum is 0
Honestly I didn't think that much but I was able to solve the question :p. My thought process was "how about I get the largest array with sum = 0 and how to do that? consider every 0 as a -1"
sick, thanks for continuing to make these
very smart. the solution is so clean
Amazing explanation today, thanks
it was great explanation, I do understand the solution after watching your video. But how coming up with such solution is not intuitive for me, could you please help with that in any way?
hey @NeetCodeIO at 0:46 wont it be !n (factorial of n) rather than n^2 (n squared) ??
n! is equal to n * n-1 * n-2 * .... * 2 * 1, while the solution at 0:46 is n + n-1 + n-2 + .... + 2 + 1 which is (n(n+1))/2 which we simplify to O(n^2)
love the solution but I aint never coming up with this during an interview without prior knowledge.
Hey @NeetCodeIO, won't it be a better solution to use double pointers one at index 0 (s) and another at index n -1 (e), and increment or decrement s and e depending on the number of 1es.
if sum(array[s:e]) * 2 > (e - s + 1), s++ if array[s] == 1 or e-- if array[e] == 1
else if sum(array[s:e]) * 2 < (e - s + 1) , s++ if array[s] == 0 or e-- if array[e] == 0
else return array[s:e].
let me know what you think.
please make complete playlist with problem sovling using python in from any online patfrom
yup
This is so intelligent and I still can’t figure out how can you come up with this solution XD
What if we count all zeroes and ones first time and will use sliding window by decreasing it from right and left. For example, we have 3 zeros and 5 ones. We will decrease the side where we have ones or zeros if we don't have ones from each side and each time update(decrease) zeros and ones values. Will it work?
Amazing :D
does it matter if the array starts with a 0?
one day ill be like you
please keep the comments NC !!
censoring dislikes from leetcode is annoying AF
how do people just come up with this stuff
Include comments! Sometimes the hardest part is intuiting the solution, so seeing how you got from Sliding Window to this Prefix Sum is interesting.
Glad to have your videos & roadmap as I prep for interviews. Thx a bunch.
am i the only one who wasn't able to pass all the testcases with this?
here's my code, just in case someone can help point out my mistake
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
zeros, ones = 0, 0
diff_index = {}
res = 0
for i, n in enumerate(nums):
if i == 0: zeros += 1
else: ones += 1
if ones - zeros not in diff_index:
diff_index[ones - zeros] = i
if ones == zeros:
res = ones + zeros
else:
idx = diff_index[ones - zeros]
res = max(res, i - idx)
return res
I guess you've already figured it out, but just in case you haven't, your code should be:
if n == 0:
zeroes += 1
else:
ones += 1
Because you need to be checking if each element of the array is equal to zero, not if the index is zero.
@@silverblade3377 Oh my. Thanks!
People are still learning dsa? Whym