Your channel is gold. Just 1 small optimisation can be not using the map but using an array to contain the sum. We can take an array of length 2*n+1 where n=length of given nums array. We can add n to each sum i.e., we can initialise our sum variable with n rather than 0. Next all the things are same. The logic is quite obvious. If the given nums array contains all 1's, then max sum possible is n and we are adding n to it, so total n+n=2n. That's why taking an array for hash of length 2*n+1. If the given nums array contains all 0's, then sum will become -n+n=0. Hence, we can accomodate all values in our 2*n+1 hash array.
Thank you mate. for the edge case when we get zero as current sum, we can just add "0: -1" in the hashmap in the start and don't have to worry about it in the code to check that edge case.
For the people who heard "Contiguous Subarray" first time. Contiguous Subarray means any part of array where no elements are skipped. [1,2,3,4,5] has [3,4,5] as contiguous subarray but [1,4,5] is not Contiguous Subarray. We can think kind of continuous subarray.
how will you get this type of IDEAS man? like replace 0 with -1 then compute the problem........this is mind-blowing. love your channel dude and thanks for making videos " SURYA PRATAP KAHAR " :)
If you are doing coding in C then will recommend you to switch to C++ as soon as you can. It will be a cakewalk to switch. C doesn't have standard libraries. You will be at ease. Believe me.
Yes plzz switch to C, it's involves tedious work even for basic things, change it ASAP, I also made this mistake so highly recommend u! Well this comment is 1 year ago M sorry but to whomsoever it may concern!
Code in Java -- @TechDose class Solution { public int findMaxLength(int[] nums) { HashMap hm = new HashMap(); int sum =0; int max=0; int temp=0; for (int i=0; i
sir, i appreciate ur method. It's nice. Maybe, i have another approach, plzz tell me whether it works or not. If not, then plz explain why? APPROACH: compute the count of zeroes and ones from the array and find min(count_of_zero, count_of_one)*2. This expression will give you maximum length of subarray. If any of these counts is/are 0, then no subarray is possible which meets the given criteria.
I had thought this as my first idea and you did too 😅 This won't work because counting is not taking contiguous element property into consideration. It may skip some elements in between and say the answer. This can work for subsequence where you can skip any element but this won't work for subarray. Take the example of 0 1 1 1 0. You method will give 4 but answer is only 2. I hope you got it :)
All good... very clear explanation as always in your channel... But, is it fair for the companies to expect someone to think of a solution for this kind of hard problem and code it in 45 minutes?
I have seen this video last month still i need to watch this video agin , i am just getting demotivated for this , why ideas are not coming in my mind ?
how does a solution strike the mind? Is it just about intuition who just a few smart people happen to have, or you get to learn a particular pattern over a long period of time by solving problems over and over?
Your last guess is right. Everyone is smart in common matters but once we talk about a specific skill then you need to train your brain over a period of time.
Had a doubt!! What if the array starts with 0 this code will not work then. For example : [0,0,1,0,1,1,1,1,0]. Can you please explain? If sum becomes -1 or -2, then it will be stored in map which might be wrong I guess? Correct me if I am wrong...
I guess u r thinking how can we have negative index, right? Well, we are not actually accesing by index but we are storing index. We are storing both key and value as pair in map. Key can have any value. So don't worry, it will work.
Thanks for the video, but how you decided to use hash map? How do you get that intuition. why not variables?. Please make a series of videos on how to get that intuition. It requires practice as suggested by many but still curious to know
I am just wondering what is wrong if we take a loop, 2 variables and then the lower count multiplied by 2 is the answer. Am I missing something from the question. private int maxLength(int[] arr){ int zeroCount =0; int oneCount =0; for(int I=0;I
@TECH DOSE To check element is present in map or not. Sometimes we write mymap[sum] and sometime we write mymap.find(sum)!= mymap.end()... Please can you explain this? Thanks.
Mymap[sum] will return value stored at key Sum (provided the entry is already present in map). Find is used to check if there is any valid entry present with the given key Sum. So, 2nd one can be used to check. 1st one is used to retrieve value when you know it's present else you want to initialise a new value.
I m loving the explanation but have a sense of guilt too that I was unable to solve it on my own. I tried and know about basic prefix sum but still loving this solution which I was unable to think of. What shall do? Is it fine?
I think when sum is zero is not handle correctly , i m getting wrong ans, Python sol: class Solution: def findMaxLength(self, nums: List[int]) -> int: n = len(nums)
sum ,c_arr = 0,0 //hash map d = dict() d[0]=-1 for i in range(n): if nums[i]: sum+=1 else: sum-=1 // checking if the key is present in hashmap if sum in d: c_arr = max(c_arr,i-d[sum]) else: d[sum]= i return c_arr
l=list(map(int,input().split())) dic={} sum=maxarray=0 for i in range(len(l)): sum+=(-1) if l[i]==0 else 1 if sum==0: maxarray=i+1 if sum not in dic.keys(): dic[sum]=i else: maxarray=max(maxarray,i-dic[sum]) print(maxarray)
It is Ternary operator. It means if mums[i] == 0 then select value -1 else select 1. After selection, we have given a shorthand addition operator to add the result to sum. So sum will be added by either -1 or 1 depending on the check I performed. I hope you got it :) It is easier than writting bunch of lines of if else statement to do it.
It is given to see if on searching the element you reached end of map or not. If you did, that means the element is not present. You can use map.count(sum)
Would you help me. How to find maximum GCD of the subarray. For eg. arr = { 2, 3,4,4,4} Here max subarray as welll as max GCD is ={4,4,4}. Help me what will be your efficient approach. @Tech Dose
@@DEEPAKYADAV-vb2ee bro remember - maximum GCD value will always be equal to the largest number present in the array. Let’s say that the largest number present in the array is X. Now, the task is to find the largest sub-array having all X.
Java Solution Map sumMap = new HashMap(); int sum = 0; int longestSubArr = 0; for (int i = 0; i < nums.length; i++) { sum += nums[i] == 0 ? -1 : 1; // make 0s as -1 and then add if (sum == 0) { longestSubArr = i + 1; // then we will put the index as the longestSubStr } else if (sumMap.get(sum) != null) { longestSubArr = Math.max(longestSubArr, i - sumMap.get(sum)); } else { sumMap.put(sum, i); } } return longestSubArr;
this is the best channel for finding best algorithm to problem. not even @neetcode can explain easy and efficient algorithm which this channel does
I was stuck on this for a while and saw 2 more videos before this. But you explained it really well. Thanks
Welcome
I agree
totally agreed
Your channel is gold. Just 1 small optimisation can be not using the map but using an array to contain the sum. We can take an array of length 2*n+1 where n=length of given nums array. We can add n to each sum i.e., we can initialise our sum variable with n rather than 0. Next all the things are same. The logic is quite obvious. If the given nums array contains all 1's, then max sum possible is n and we are adding n to it, so total n+n=2n. That's why taking an array for hash of length 2*n+1. If the given nums array contains all 0's, then sum will become -n+n=0. Hence, we can accomodate all values in our 2*n+1 hash array.
👍🏼
The best explanation for this problem! Good Job!
Thanks :)
Thank you mate. for the edge case when we get zero as current sum, we can just add "0: -1" in the hashmap in the start and don't have to worry about it in the code to check that edge case.
I really love your videos. The explanation is quite crisp and clear. Keep posting. Thankyou.
Welcome :)
Ur channel is a gem bro.I feel lucky to be a subscriber😅 .All the best bro..🙌🙌
Thanks :)
Thanks very much, I completely understand your explanation, great job.
Thanks :)
For the people who heard "Contiguous Subarray" first time.
Contiguous Subarray means any part of array where no elements are skipped. [1,2,3,4,5] has [3,4,5] as contiguous subarray but [1,4,5] is not Contiguous Subarray. We can think kind of continuous subarray.
Nice Explanation !!...I was waiting for ur video.
Thanks :)
Good Explanation. Clear & concise.
This question is good & you explain it the nice way. I also have a similar approach, but your code is more compact.
Thanks :)
@@techdose4u Aap bhagvaan ho kya?
You are doing a good job...following all your videos. ..keep uploading.
Thanks :)
I was stuck on this but you explained it well. Im just thinking no way I would know this solution unless Ive seen it :D
Thank you. It was a good explanation
how will you get this type of IDEAS man? like replace 0 with -1 then compute the problem........this is mind-blowing. love your channel dude and thanks for making videos " SURYA PRATAP KAHAR " :)
Actually I had seen such trickery in some other problems. So whatever is seen, quickly comes into mind 😅
This channel is gold.
❤️
The is the best explanation I've seen
Very good explanation and its very helpful
Thanks :)
NICE SUPER EXCELLENT MOTIVATED
Your approach is great. I used map as well but very nasty. Great explanation.
Sir,could u pls explain the c code based on whatever u will say the problem so that it will be better .. u r the best tutor I never seen really
If you are doing coding in C then will recommend you to switch to C++ as soon as you can. It will be a cakewalk to switch. C doesn't have standard libraries. You will be at ease. Believe me.
As per our placement the companies will give more preference to c languge so tht I'm learning
I heard this the first time. Can you name some companies who prefer C over CPP?
Yes plzz switch to C, it's involves tedious work even for basic things, change it ASAP, I also made this mistake so highly recommend u! Well this comment is 1 year ago
M sorry but to whomsoever it may concern!
@@techdose4u better move to python 🐍 sir
Thanks for the explanation :)
Welcome 😄
Code in Java -- @TechDose
class Solution {
public int findMaxLength(int[] nums) {
HashMap hm = new HashMap();
int sum =0;
int max=0;
int temp=0;
for (int i=0; i
👍🏼
very clear explanation. Thank you so much.
Welcome
Instead of having the condition sum == 0, we can initialize the map mymap[0] = -1 and when we encounter 0, i+1 will be added to longest_subarray.
We could have done map[0] = 1 and then iterated.
@@techdose4u shouldn't it be map[0] = -1 and not map[0] = 1 because this way, when sum is 0, it will be i - (-1) = i + 1
The idea is to add. If you take minus sign then take -1. This time around I solved with 1 😅 It all depends on how you manipulate the calculation.
True, I said -1 in agreement to the equation in the video "longest_subarray = i - mymap[sum]" where using +1 could make it wrong.
Great explanation, helped me solve for sure!
Keep posting. Thankyou.
Welcome 😄
Really Impressive. Helped a lot !!
Welcome
Python3 code:
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
dic = {}
sum = count = 0
for i in range(len(nums)):
sum += 1 if nums[i] == 1 else -1
if sum == 0:
count = max(count,i + 1)
elif(sum in dic):
count = max(count,i - dic[sum])
else:
dic[sum] = i
return count
Great explanation ........Thank you sir
That's really amazing explanation
Thanks
Very well explained. Thank you.
Welcome 😄
Thanks for the clear explanation
Welcome 😊
Great explanation as always.
Thanks :)
sir, i appreciate ur method. It's nice. Maybe, i have another approach, plzz tell me whether it works or not. If not, then plz explain why?
APPROACH: compute the count of zeroes and ones from the array and find min(count_of_zero, count_of_one)*2. This expression will give you maximum length of subarray. If any of these counts is/are 0, then no subarray is possible which meets the given criteria.
I had thought this as my first idea and you did too 😅 This won't work because counting is not taking contiguous element property into consideration. It may skip some elements in between and say the answer. This can work for subsequence where you can skip any element but this won't work for subarray. Take the example of 0 1 1 1 0. You method will give 4 but answer is only 2. I hope you got it :)
@@techdose4u ohhkk... i got it
:)
hahaha bhaiya i too thought same for the first time 😅
I tried this one too at first and got WA XD
*Closer to prefix sums*
Great Explanation ❤
brilliant work!!!!!!!!!!!!!!!!!!!!
Thanks :)
Great work.
Thanks :)
Nice explanation
Thanks 😊
very good explanation
Awesome explanation!
Thanks :)
the best explanation!!
Thanks :)
Nicely Explained!
Thanks :)
Nice explanation !!!
Thanks
How you build your such good concepts?? To produce optimal solutions
First I think atleast one solution and try solving. If it works then I try optimizing different steps for that problem. This method works for me.
Nice approach
:)
Very well explained
All good... very clear explanation as always in your channel...
But, is it fair for the companies to expect someone to think of a solution for this kind of hard problem and code it in 45 minutes?
Generally you won't be asked hard problems.
I have seen this video last month still i need to watch this video agin , i am just getting demotivated for this , why ideas are not coming in my mind ?
You should fully understand a problem and then solve similar problems yourself in order to remeber it.
how does a solution strike the mind? Is it just about intuition who just a few smart people happen to have, or you get to learn a particular pattern over a long period of time by solving problems over and over?
Your last guess is right. Everyone is smart in common matters but once we talk about a specific skill then you need to train your brain over a period of time.
python
data = nums
hm = {}
res = 0
ctr = 0
for i in range(len(data)):
if data[i] == 0:
ctr -= 1
else:
ctr += 1
if ctr == 0 and i+1 > res:
res = i+1
if ctr not in hm:
hm[ctr] = i
else:
val = i-hm[ctr]
if val > res:
res = val
return res
I really appreciate your thought process
Had a doubt!! What if the array starts with 0 this code will not work then. For example : [0,0,1,0,1,1,1,1,0]. Can you please explain? If sum becomes -1 or -2, then it will be stored in map which might be wrong I guess? Correct me if I am wrong...
I guess u r thinking how can we have negative index, right? Well, we are not actually accesing by index but we are storing index. We are storing both key and value as pair in map. Key can have any value. So don't worry, it will work.
Thanks brother, explanation was so good , i could solve without waiting for code section.
welcome :)
Thanks for the video, but how you decided to use hash map? How do you get that intuition. why not variables?. Please make a series of videos on how to get that intuition. It requires practice as suggested by many but still curious to know
Will make it in near future for sure :)
I am just wondering what is wrong if we take a loop, 2 variables and then the lower count multiplied by 2 is the answer. Am I missing something from the question.
private int maxLength(int[] arr){
int zeroCount =0;
int oneCount =0;
for(int I=0;I
@TECH DOSE To check element is present in map or not. Sometimes we write mymap[sum] and sometime we write mymap.find(sum)!= mymap.end()... Please can you explain this? Thanks.
Mymap[sum] will return value stored at key Sum (provided the entry is already present in map). Find is used to check if there is any valid entry present with the given key Sum. So, 2nd one can be used to check. 1st one is used to retrieve value when you know it's present else you want to initialise a new value.
@@techdose4u Thanks for the response.
Can be done with stack as well
Code please :)
can we use the sliding window technique ?
bro . you have done a excepional job .youre better than nick white kelvin naugton . pls dont go fast while u teach . thanks
Thanks bro :)
@@techdose4u go slow while u teach bro . because we are like small kids in problem solving . and the way u teach is amazing keep it up i appreciate it
bhaiya can't we use stack.
int findMaxLength(vector& nums) {
int s,i,count=0,max=0;
s=nums.size();
stackst;
st.push(nums[0]);
for(i=1;i
I m loving the explanation but have a sense of guilt too that I was unable to solve it on my own. I tried and know about basic prefix sum but still loving this solution which I was unable to think of. What shall do? Is it fine?
It's fine. Just don't watch the code implementation and try yourself. If you can't do then see it :)
I think when sum is zero is not handle correctly , i m getting wrong ans,
Python sol:
class Solution:
def findMaxLength(self, nums: List[int]) -> int:
n = len(nums)
sum ,c_arr = 0,0
//hash map
d = dict()
d[0]=-1
for i in range(n):
if nums[i]:
sum+=1
else:
sum-=1
// checking if the key is present in hashmap
if sum in d:
c_arr = max(c_arr,i-d[sum])
else:
d[sum]= i
return c_arr
l=list(map(int,input().split()))
dic={}
sum=maxarray=0
for i in range(len(l)):
sum+=(-1) if l[i]==0 else 1
if sum==0:
maxarray=i+1
if sum not in dic.keys():
dic[sum]=i
else:
maxarray=max(maxarray,i-dic[sum])
print(maxarray)
👍
It helped!
:)
Will you keep all the videos free in future or you will move to a paid platform ?
Problems will be free. I will include donations in near future. If it goes well then everything will be free forever.
can you explain what this line means?
sum += nums[i]==0?-1:1;
It is Ternary operator. It means if mums[i] == 0 then select value -1 else select 1. After selection, we have given a shorthand addition operator to add the result to sum. So sum will be added by either -1 or 1 depending on the check I performed. I hope you got it :) It is easier than writting bunch of lines of if else statement to do it.
if(nums[i] == 0) {
sum = sum-1;
} else sum = sum+1
Why did you compare mymap.find(sum) with mymap.end()?
Can't be simply
If(mymap.find(sum))
It is given to see if on searching the element you reached end of map or not. If you did, that means the element is not present. You can use map.count(sum)
Okay. Got it!!
👍
thank you so much ..
Welcome :)
👌👌👌👌👌👌
:)
is it a dp problem?
Thank you!!!!
Welcome :)
can we solve it without map
Thanku sir.
Welcome :)
Would you help me.
How to find maximum GCD of the subarray.
For eg. arr = { 2, 3,4,4,4}
Here max subarray as welll as max GCD is ={4,4,4}.
Help me what will be your efficient approach.
@Tech Dose
What can be the size of subarray?
@@techdose4u all the size of subarray >=2 of the given array
@@techdose4u it is just same as the max sum of the subarray. But here instead of finding the sum, we have to find the max gcd .
@@DEEPAKYADAV-vb2ee bro remember - maximum GCD value will always be equal to the largest number present in the array. Let’s say that the largest number present in the array is X. Now, the task is to find the largest sub-array having all X.
Max gcd will always be of length 2. So find all possible subarray gcds of length 2. There will be N-1 such subarrays.
int findMaxLength(vector& nums) {
// Fast I/O
ios_base::sync_with_stdio(false);
cin.tie(NULL);
int n = nums.size();
if(n == 0 or n == 1)
return 0;
unordered_map mp;
int res = 0, sum = 0;
mp[0] = -1; //for handling first element as 0 so index is -1 default
for(int i=0; i
You just explained the solution
But there is no intuition
can you give me solution for java
Laga de bhai sum wala concept 0 ko -1 rakhne wala
😂
@@techdose4u bhai placement h 🤣bta de kaise padu
Bhai target company btao...fir kuchh btate hain 😅
@@techdose4u bhai flipkart ya amazon
2-0+1 = 2.
You corrected. Nice.
Naruto fan spotted
I'm sorry but you were a bit hard to follow along
Java Solution
Map sumMap = new HashMap();
int sum = 0;
int longestSubArr = 0;
for (int i = 0; i < nums.length; i++) {
sum += nums[i] == 0 ? -1 : 1; // make 0s as -1 and then add
if (sum == 0) {
longestSubArr = i + 1; // then we will put the index as the longestSubStr
} else if (sumMap.get(sum) != null) {
longestSubArr = Math.max(longestSubArr, i - sumMap.get(sum));
} else {
sumMap.put(sum, i);
}
}
return longestSubArr;