Contiguous array | Leetcode

[@anand_dudi]

this is the best channel for finding best algorithm to problem. not even @neetcode can explain easy and efficient algorithm which this channel does

[@shivanggupta5421]

I was stuck on this for a while and saw 2 more videos before this. But you explained it really well. Thanks

[@techdose4u]

Welcome

[@RajVeerEkSoch]

I agree

[@abdulrehmanamer4252]

totally agreed

[@goutamkundu6392]

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.

[@techdose4u]

👍🏼

[@aadil4236]

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.

[@gourabbanerjee4152]

The best explanation for this problem! Good Job!

[@techdose4u]

Thanks :)

[@PremPal-uy4nm]

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.

[@lemax2980]

Ur channel is a gem bro.I feel lucky to be a subscriber😅 .All the best bro..🙌🙌

[@techdose4u]

Thanks :)

[@abhijitbandyopadhyay4821]

Good Explanation. Clear & concise.

[@qilinzhang6958]

Thanks very much, I completely understand your explanation, great job.

[@techdose4u]

Thanks :)

[@aswathsrimarir2501]

You are doing a good job...following all your videos. ..keep uploading.

[@techdose4u]

Thanks :)

[@pranayraj7938]

Nice Explanation !!...I was waiting for ur video.

[@techdose4u]

Thanks :)

[@juuzousuzuya69]

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

[@aparnamane1164]

I really love your videos. The explanation is quite crisp and clear. Keep posting. Thankyou.

[@techdose4u]

Welcome :)

[@sarvesh6785]

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

[@najimali32]

This question is good & you explain it the nice way. I also have a similar approach, but your code is more compact.

[@techdose4u]

Thanks :)

[@amandeepnokhwal2977]

@@techdose4u Aap bhagvaan ho kya?

[@venkateshthirunagiri85]

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 " :)

[@techdose4u]

Actually I had seen such trickery in some other problems. So whatever is seen, quickly comes into mind 😅

[@bisheshwardevsharma3243]

Thank you. It was a good explanation

[@ryanchen467]

The is the best explanation I've seen

[@ganeshjaggineni4097]

NICE SUPER EXCELLENT MOTIVATED

[@meet2637]

This channel is gold.

[@techdose4u]

❤️

[@anjalisinha3377]

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

[@techdose4u]

👍🏼

[@Yash-uk8ib]

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.

[@techdose4u]

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 :)

[@Yash-uk8ib]

@@techdose4u ohhkk... i got it

[@techdose4u]

:)

[@stankafan6688]

hahaha bhaiya i too thought same for the first time 😅

[@soumavabanerjee5925]

I tried this one too at first and got WA XD

[@AnkitRaj-jn8ew]

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.

[@techdose4u]

We could have done map[0] = 1 and then iterated.

[@AnkitRaj-jn8ew]

@@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

[@techdose4u]

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.

[@AnkitRaj-jn8ew]

True, I said -1 in agreement to the equation in the video "longest_subarray = i - mymap[sum]" where using +1 could make it wrong.

[@sumitSharma-ed5mi]

Very good explanation and its very helpful

[@techdose4u]

Thanks :)

[@Giri14_18]

Great explanation ........Thank you sir

[@dhanashreegodase4445]

Keep posting. Thankyou.

[@techdose4u]

Welcome 😄

[@subham-raj]

*Closer to prefix sums*

[@aviligondagowtham1153]

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

[@techdose4u]

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.

[@aviligondagowtham1153]

As per our placement the companies will give more preference to c languge so tht I'm learning

[@techdose4u]

I heard this the first time. Can you name some companies who prefer C over CPP?

[@akshitajha1209]

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!

[@pravyn350]

@@techdose4u better move to python 🐍 sir

[@akhilesh59]

Thanks for the explanation :)

[@techdose4u]

Welcome 😄

[@ahmedfouzan]

Thanks for the clear explanation

[@techdose4u]

Welcome 😊

[@mohamedhesham6008]

That's really amazing explanation

[@techdose4u]

Thanks

[@halfaddercircuit]

Your approach is great. I used map as well but very nasty. Great explanation.

[@ganakkathuria4893]

Nice explanation

[@techdose4u]

Thanks 😊

[@chrisjurgens8043]

Great explanation, helped me solve for sure!

[@akshayaamar9825]

Very well explained. Thank you.

[@techdose4u]

Welcome 😄

[@priyamani4349]

Great work.

[@techdose4u]

Thanks :)

[@kumarswamy3554]

very clear explanation. Thank you so much.

[@techdose4u]

Welcome

[@saurabh.gupta22]

Great Explanation ❤

[@abhishekkumarjhariya1340]

Great explanation as always.

[@techdose4u]

Thanks :)

[@suryajanardhan]

very good explanation

[@praveenchouhan6388]

brilliant work!!!!!!!!!!!!!!!!!!!!

[@techdose4u]

Thanks :)

[@tanishqaggarwal1197]

Nice approach

[@techdose4u]

:)

[@ajaywadhwa3398]

Really Impressive. Helped a lot !!

[@techdose4u]

Welcome

[@kushgupta1187]

Very well explained

[@debashisdas6593]

Nice explanation !!!

[@techdose4u]

Thanks

[@priyankadey3337]

Awesome explanation!

[@techdose4u]

Thanks :)

[@ishmeetbindra5428]

Nicely Explained!

[@techdose4u]

Thanks :)

[@sujiths9199]

I really appreciate your thought process

[@audioplatform6299]

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?

[@techdose4u]

Generally you won't be asked hard problems.

[@Learner010]

the best explanation!!

[@techdose4u]

Thanks :)

[@ryan.aquino]

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

[@shubhamgarg7198]

How you build your such good concepts?? To produce optimal solutions

[@techdose4u]

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.

[@jaydeepmahajan6598]

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 ?

[@techdose4u]

You should fully understand a problem and then solve similar problems yourself in order to remeber it.

[@mayankchauhan6680]

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?

[@techdose4u]

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.

[@nidhisingh25_]

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...

[@techdose4u]

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.

[@damodaranm3044]

bro . you have done a excepional job .youre better than nick white kelvin naugton . pls dont go fast while u teach . thanks

[@techdose4u]

Thanks bro :)

[@damodaranm3044]

@@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

[@syed7996]

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

[@techdose4u]

Will make it in near future for sure :)

[@yashshreeshinde4394]

Thank you!!!!

[@techdose4u]

Welcome :)

[@ssaha7714]

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

[@manjunathp9466]

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)

[@techdose4u]

👍

[@parekshamanchanda8083]

Can be done with stack as well

[@techdose4u]

Code please :)

[@amanvijayvargiya3468]

thank you so much ..

[@techdose4u]

Welcome :)

[@locusoflearning]

Thanku sir.

[@techdose4u]

Welcome :)

[@muskanmangal8938]

It helped!

[@techdose4u]

:)

[@rahulsaini202]

@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.

[@techdose4u]

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.

[@rahulsaini202]

@@techdose4u Thanks for the response.

[@stankafan6688]

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

[@ApexPlayground_divine]

Thanks brother, explanation was so good , i could solve without waiting for code section.

[@techdose4u]

welcome :)

[@akshitajha1209]

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?

[@techdose4u]

It's fine. Just don't watch the code implementation and try yourself. If you can't do then see it :)

[@rahulchaubey8988]

👌👌👌👌👌👌

[@techdose4u]

:)

[@najimali32]

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

[@vinoltauro9160]

can we use the sliding window technique ?

[@akashmittal7795]

can you explain what this line means? sum += nums[i]==0?-1:1;

[@techdose4u]

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.

[@mayankchauhan6680]

if(nums[i] == 0) { sum = sum-1; } else sum = sum+1

[@muskaangupta4920]

Why did you compare mymap.find(sum) with mymap.end()? Can't be simply If(mymap.find(sum))

[@techdose4u]

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)

[@muskaangupta4920]

Okay. Got it!!

[@techdose4u]

👍

[@subhadippatra7930]

Will you keep all the videos free in future or you will move to a paid platform ?

[@techdose4u]

Problems will be free. I will include donations in near future. If it goes well then everything will be free forever.

[@ankitchaturvedi2941]

can we solve it without map

[@DEEPAKYADAV-vb2ee]

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

[@techdose4u]

What can be the size of subarray?

[@DEEPAKYADAV-vb2ee]

@@techdose4u all the size of subarray >=2 of the given array

[@DEEPAKYADAV-vb2ee]

@@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 .

[@spetsnaz_2]

@@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.

[@techdose4u]

Max gcd will always be of length 2. So find all possible subarray gcds of length 2. There will be N-1 such subarrays.

[@baxtables]

is it a dp problem?

[@spetsnaz_2]

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

[@hemantranjan2297]

2-0+1 = 2.

[@hemantranjan2297]

You corrected. Nice.

[@sahilanand30]

You just explained the solution But there is no intuition

[@nuclearbaba1769]

can you give me solution for java

[@lakshyavijh1249]

Laga de bhai sum wala concept 0 ko -1 rakhne wala

[@techdose4u]

😂

[@lakshyavijh1249]

@@techdose4u bhai placement h 🤣bta de kaise padu

[@techdose4u]

Bhai target company btao...fir kuchh btate hain 😅

[@lakshyavijh1249]

@@techdose4u bhai flipkart ya amazon

[@abhinavsingh8675]

Naruto fan spotted

[@BRBallin1]

I'm sorry but you were a bit hard to follow along

[@gauthamsssomanna9388]

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;