Contiguous array | Leetcode #525

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

[shivanggupta]

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

[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

[goutamkundu]

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.

[aadil]

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.

[gourabbanerjee]

The best explanation for this problem! Good Job!

[lemax]

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

[PremPal-uynm]

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.

[najimali]

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

[aparnamane]

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

[juuzousuzuya]

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

[venkateshthirunagiri]

how will you get this type of IDEAS man? like replace 0 with -1 then compute the is mind-blowing. love your channel dude and thanks for making videos " SURYA PRATAP KAHAR " :)

[qilin]

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

[pranayraj]

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

[abhijitbandyopadhyay]

Good Explanation. Clear & concise.

[aswathsrimarir]

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

[ryanchen]

The is the best explanation I've seen

[aviligondagowtham]

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

[sarvesh]

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

[Yash-ukib]

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.

[halfaddercircuit]

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