Contiguous array | Leetcode
Vložit
- čas přidán 12. 04. 2020
- This video explains a very important programming interview problem which is to find the count of all contiguous array will equal number of zeroes and ones. This problem is one the most important problem type and has also repeated in google kickstart 2020 round C question 3 which is perfect subarray. I have explained the intuition for solving this problem and then showed a solution using map. At the end of the video, i have explained the CODE for the algorithm and as usual, the CODE LINK is given below. If you find any difficulty or have any query then do COMMENT below. PLEASE help our channel by SUBSCRIBING and LIKE our video if you found it helpful...CYA :)
CODE LINK: gist.github.com/SuryaPratapK/...
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
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 but you explained it well. Im just thinking no way I would know this solution unless Ive seen it :D
I really love your videos. The explanation is quite crisp and clear. Keep posting. Thankyou.
Welcome :)
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.
Thank you. It was a good explanation
You are doing a good job...following all your videos. ..keep uploading.
Thanks :)
Your approach is great. I used map as well but very nasty. Great explanation.
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.
👍🏼
Thanks very much, I completely understand your explanation, great job.
Thanks :)
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?
Nice Explanation !!...I was waiting for ur video.
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.
Great explanation, helped me solve for sure!
The is the best explanation I've seen
Great explanation ........Thank you sir
Ur channel is a gem bro.I feel lucky to be a subscriber😅 .All the best bro..🙌🙌
Thanks :)
This channel is gold.
❤️
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 😅
Great Explanation ❤
Great explanation as always.
Thanks :)
NICE SUPER EXCELLENT MOTIVATED
*Closer to prefix sums*
Very well explained
Thanks for the explanation :)
Welcome 😄
That's really amazing explanation
Thanks
Very well explained. Thank you.
Welcome 😄
Really Impressive. Helped a lot !!
Welcome
very clear explanation. Thank you so much.
Welcome
Great work.
Thanks :)
very good explanation
Keep posting. Thankyou.
Welcome 😄
Nicely Explained!
Thanks :)
brilliant work!!!!!!!!!!!!!!!!!!!!
Thanks :)
Very good explanation and its very helpful
Thanks :)
Thanks for the clear explanation
Welcome 😊
I really appreciate your thought process
the best explanation!!
Thanks :)
Nice approach
:)
Nice explanation !!!
Thanks
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!
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
Nice explanation
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
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.
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 :)
thank you so much ..
Welcome :)
It helped!
:)
Thank you!!!!
Welcome :)
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.
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.
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
👌👌👌👌👌👌
:)
can we use the sliding window technique ?
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
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.
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
👍🏼
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.
Thanku sir.
Welcome :)
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.
Sir I have a doubt!.. I am using python for ds. Can I use inbuilt function like dict() or keys() in coding interviews for hashing??...will this works(I.e runtime error may comes)..not only this there are many inbuilt function in python. Is it a good practice to use them.
Avoid inbuilt functions but use basic ones. Dict and keys are fine. Mostly you will be good. But if are required to implement an algo then don't just use inbuilt fn to solve it. Like you are asked to calculate lower bound of a number then use binary search instead of lower bound built in fn. If you are asked a larger problem to solve where you need to find lower bound then you can use built in fn.
Thnks sir😃
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
@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.
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
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
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 :)
is it a dp problem?
Can be done with stack as well
Code please :)
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 we solve it without map
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
You just explained the solution
But there is no intuition
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!!
👍
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.
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)
👍
2-0+1 = 2.
You corrected. Nice.
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
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
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;
Awesome explanation!
Thanks :)