LeetCode 525. Contiguous Array (Algorithm Explained)

Preparing For Your Coding Interviews? Use These Resources
————————————————————

Other Social Media
----------------------------------------------

Show Support
------------------------------------------------------------------------------

#coding #programming #softwareengineering

[YNA]

Nick : "It's not that hard, it could be easy even."
Also Nick Submissions : Multiple Rejection

Cmon dude...

[calfland]

It is definitely a medium problem. counts.put(0, -1) only this line could kill 90% people if they have never study this problem before.

[oscaropdyou]

If there is confusion on why count "0" is initialised with -1 index, this is because before we start, we start with count of 0. If we get lets say [0, 1], then it would go to -1 and 0. And as we have initialised first index of 0 as -1. And length would be -1 to 1(current index when count reached 0).

[Dan-tggs]

i feel that this solution was hard to come up with without already seeing some kind of pattern of this question before. When I saw the solution, I understood it, but I'm wondering if these types of questions will get intuitive with more practice? Is this considered DP?

[visheshmangla]

Consider two indices i and j where i<j . If the difference of counts of ones and zeroes(for i and j individually) from the start to i and j have same difference then surely the difference or the extra count lies towards the left or in other words the centre portion has same counts because we have counts at i = ones at i - zeroes at i from start to that point and similarly for j. Also if count_total is 0 at both indices then there is nothing at left and then i will be 0 in that case but we will take -1 because we want length between i(include) and j(included). like 100 -11 = 89 but 11 to 100 are 90 numbers.

[manjorysaran]

u r really good! how did you practice and for how long before you could code like this?

[subhedarsanchay]

Hey Nick, great video. Thanks for all of your hard work. Just have a minor suggestion. I have seen a bunch of your videos and you almost tend to size the problem by saying "oh this is an easy problem" or "this problem is super simple". This might discourage the viewer into thinking they can't even solve these easy problem. And believe me, most viewers who are watching your videos are the folks who could not solve this problem and hence are looking to understand the solution. I'd appreciate if you could stop doing that. Let me know if I am being too sensitive. Again, I am your youtube subscriber and thank you!

[jhonnymoreira]

Thanks for clearing the problem and going over the solution. I was having a hard time understanding the concept of `contiguous` (non-native english speaker), and the longer example plus your code helped a lot.

[Whaleshamu]

i understand that we are putting -1 for 0, coz we have not seen 0 yet. But why we are initially putting 0 inside map?

[vinayprabhakar]

Can u plz tell why we added 0, -1 into our hashmap before going through the array didn't get that part

[abulaman]

I thought of someway of substracting the number of zeros and ones to arrive at the solution....,
Wow man, love your brains

[abhishekkrishna]

this is a fabulous way of looking at the problem. i wouldn't have comeup with this solution.

[ahjiba]

initially thought of this problem as max contiguous subarray equals k, where k = 0 and all 0s are converted into -1, hope that helps anyone thinking through this problem

[madhurbhargava]

Did not really get why this video was created if the whole idea was to just read the solution from the solutions section.

[duyetpham]

i try many ways before view video, this is great. It is simple and power, thank you.

[Mohit-nnbt]

I liked how you explained what is binary :-)

[RishiRaj-dlmg]

Can we solve this using bottom up dp???

[ianchui]

awesome work! helped me very much. I did not enjoy going through that animation at all lmaoo

[officialspock]

I don't understand the example, why is [0, 1] maxlen is 2, and [0, 1, 0] maxlen is still 2, I had a look at the discussion and get more confused... I hope someone can explain this properly before I can formulate a logic to solve this.
[0, 0, 0, 1, 1, 2, 1] = 6 // other numbers than 0 and 1 are ignored
[0, 1, 0, 1] = 4 // so this is 4, why?
[0, 1, 0, 1, 1] = 4 // this is also 4... so there is some symetry condition??
[0, 0, 1, 0, 0, 0, 1, 1] = 6 // this is 6?? I do not see why. I would have expected 4