Maximal Square of Ones (LeetCode Day 27)

[@ShivamSingh-vu8vq]

I really gained confidence in DP by watching your video , thanks Errichto !!

[@johnvanschultz2297]

My man didn't even bother running the tests he went right to submit. I will never be that brave

[@gompro]

Such a perfect visualization of the problem. Absolutely my go-to channel for algorithms.

[@dz_s]

One of the best competitive programming channels to my mind. I would really like to see special playlist with "Hard" level problems (leetcode examples possible). To me it's still quite hard to see patterns in such kind of problems. Thanks!

[@fycode]

Yeah, that would be really helpful. I am trying to crack Hard problems so such resources would be a gold mine for sure :)

[@BedoEbied]

Best free explanation in the market, love you dude! ❤️

[@adibhasan8114]

ABSOLUTE MASTERCLASS EXPLANATION !!! THANKS A LOT ERRICHTO LOOKING FORWARD TO THE 2D PREFFIX SUM SOLUTION !!!!

[@ayushpathak4918]

best explanation for this question till now.... Understood it after two days.. Thanks man

[@whitesalmon0925]

the first 2:45 mins were ASMR right there!! I had no idea what is going on, but I enjoyed watching them :). Also the explanation at 8:40 was awesome

[@limakbear7029]

Exactly, I got the idea, DP is awesome

[@shivanshkasaudhan4130]

Thanks Errichto, the solution was really an out of the box solution.

[@HalocaneJump]

Love your explanations! So simple but clearly communicated and effective!

[@Kranach777]

I knew I had to use DP for this problem, but I couldnt figure out the idea how to count dp[i][j]. I struggled for some time but after an hour I gave up and looked up solution. Need some more dp practice I guess ;P

[@miteshkumar3183]

I was trying to store the maximum height and maximum width separately, and then I realized that it is a square so they both have to be the same.

[@ZzwhiskeybkszZ]

me too! I knew it was DP but couldn't derive the relation. Keep practicing!

[@kalapnaa8623]

An N*N matrix containing 1s and Os is given as the input to the program. The program must print the number of 2x2 unit matrices in the given matrix. A matrix is said to be unit matrix if all the integers are 1. Also, consider the overlapping matrices.

[@kalapnaa8623]

Ans plz

[@sankarraja5709]

Ans plz

[@rajaryansingh3156]

I m struggling with dp and recursion, but your videos help a lot. 💓

[@vincentchang8748]

my brain is so smooth

[@bethsuni4011]

Going through the test case step by step was nice.

[@hilmybyte]

the best explanation for me as a beginner

[@uneq9589]

Errichto be like, "And this is the hardest part of the problem..." + " ..but not for me :P"

[@vijay6877]

tbh I really wanted to quit programming it looks like this is not for me. but whenever I watch your video this give me little hope. and I Think I should give it one more try. Thanks Errichto.

[@gianlucavigano711]

Don't give up!! If you like programming you should never stop practicing it... with time, hard work and passion you'll see great improvements, as with everything

[@milanboroja7094]

Who can press dislike on this ?! You are awesome man!

[@saicharan882]

Great video. Nice explanation. New thing learned is how to use min of 3 numbers.

[@romokdas8494]

When to use dynamic programming instead of greedy solutions in optimization problems? Do you use some tricks or its pure intuition?

[@Errichto]

I explained my intuition and general approach in a series of 3 dp lectures, find them in my playlists kzbin.info/door/Br_Fu6q9iHYQCh13jmpbrgplaylists

[@sauravpaul4131]

Thank you for this great explanation.

[@superdonkhalil]

wow your video really helps me to understand algorithm! thx!

[@kemosabe6521]

I would love to see Top-down Approach instead, as yesterday. Well i got some hint and will try to make my code works. 😁 FYI i am very beginner in Dp nd solved it similar way around 4hr after heavy debugging ☹️

[@imdeadshot3632]

hard to derive prefix sum for 2d arrays, a video on that would be of much help! also, i learnt min(3 elements) can be done calling once and wrapping all inside {}, till now i used to do min(a,b,c) = min(min(a,b), c) . Thanks a lot for this trivial yet code shortening trick!

[@kacperozieblowski3809]

I saw that when you didn't include the dp[row-1][col-1] and I was so proud of myself for seeing it lol. Interesting problem btw.

[@satyakimajumder1976]

Fantastic explanation ! I request you to cover subsequence and subarray problems, like getting subsequences of array whose length is a power of 2 and find the maximum element in each subsequence or subarray such that the sum of those is maximum (For example).

[@БлаговестГеоргиев-й9р]

What if problem was to find max rectangle in matrix ,I cant do this

[@Errichto]

It's a much much harder problem then. The solution in Polish is here, you can read code at the bottom www.deltami.edu.pl/temat/informatyka/algorytmy/2015/10/27/Zliczamy_puste_prostokaty/

[@sourabhkhandelwal1568]

First try the easier version. The easier version is to find the Maximum Rectangular Area in a Histogram. A Histogram is basically an Array of non negative numbers, the value at the ith index represents the height of the rectangular bar at the Index. So, the Histogram is essentially an array of unit width rectangles where the height is given in an array. The fastest approach to solve this problem is using a stack. The problem you are asking is basically an extension of the above problem.

[@БлаговестГеоргиев-й9р]

@@sourabhkhandelwal1568 that is my solution for histogram,now i will think about max rect in matrix #include using namespace std; int h[1000]; int main () { int n; cin>>n; int maxh=0,minh=999999999; for(int i=0;i>h[i];maxh=max(maxh,h[i]);minh=min(minh,h[i]);} int ans=0; for(int p=minh;p

[@lovleshbhatt7797]

​@@Errichto My approach is:-> We just make an 2D array of data type pair and use dp , but at every point for the first element of pair i,e, dp[i][j].first = dp[i-1][j]+1; // consider for find the max length vertically similarly dp[i][j].second=dp[i][j-1]+1; // consider for finding the max length horizontally Note-: if at any point mat[i][j]=0, we initialise dp[i][j].first=0; dp[i][j].second=0; Also use a 2 varible max_x, max_y to store the max value of dp[i][j].first and dp[i][j].second at every instance of traversing Thank You!! BTW BIG FAN, AND HUGE LOVE & RESPECT FROM INDIA

[@joshmiller7748]

Is www.geeksforgeeks.org/maximum-size-rectangle-binary-sub-matrix-1s/ what you are looking for?

[@joshmiller7748]

Hi Errichto. I am a big fan of your channel. I am completely new to programming, only know HTML and CSS. I want to learn JavaScript and want a book, what book would you suggest that teaches from ground up? Many books seem to assume that you have already little experience and know basics. Which book would you recommend that teaches from ground up?

[@satyammishra-xb3hs]

Best Explanation of this problem on yt. Can anyone suggest more problems like this for practice??

[@sounishnath513]

Genius like every alltime

[@ayushkhandelwal6777]

New to this channels just clicked on the video and at the end like and subscribed dude how much years did it took u to reach at this level

[@shivaraj-bh]

I first solved the brute Force way O(n^4), then I improved the solution using 2d prefix sums in O(n^3) (both of which were accepted), then I solved it using DP O(n^2) time and O(n^2) space... Went through the solution and then solved it in O(n) space.

[@barongrmel3797]

I used prefix sum and binary search, but this idea is was really neat

[@judgebot7353]

You're just awesome mate!

[@ankursuri3853]

You are a genius dude! You rock!

[@nitindas208]

Understanding your explanation is easy but how do come up with these types of solution in contest??

[@TwoTeaTee]

Such a great explaination! 🔥

[@sahilanand30]

Best explanation

[@smoothCriminaI]

Excellent explanation 😊

[@yashrastogi3726]

Such a easy question , but after seeing your explanation 😀

[@leetcodesolver9092]

Quite impressive solution and really nice explanation. I really missed such a brilliant solution and went with stack based solution to achieve same time space complexity. By the way, is there any simpler way to solve the same problem if it asks for largest Rectangle instead of largest Square?

[@Errichto]

Copying from another comment: It's a much much harder problem then. The solution in Polish is here, you can read code at the bottom www.deltami.edu.pl/temat/informatyka/algorytmy/2015/10/27/Zliczamy_puste_prostokaty/

[@akashdubey8341]

What's the stack based solution

[@arsenypogosov7206]

​@@Errichto It seems to be an O(n^2) solution. Actually you can solve it in O(n). I can describe the solution if anyone is interested.

[@juanfeliperubio137]

What if we wanted to find the maximal rectangle of one's? Thanks for your videos!

[@mandavasairaghavendradines6582]

Awsome explanation!!

[@axlrose5082]

I'm just on the easy hackerrank's ones, idk what I'm doing here but nice videos xD

[@__________________________6910]

1 min 30sec are you kidding me. You are god

[@FirefoxGuy18]

thank you so much, great way to explain

[@egor.okhterov]

Could you, please, compare this problem with finding the largest rectangle in the same matrix? Why doesn't the same DP approach cannot be used for finding the largest rectangle?

[@toekneema]

Great visual

[@mdfahad2726]

Can you tell about the timer you use. I want to practice some problem with some time constraints.

[@imsiddu]

please make a video on explaining your template for debugging...

[@lovvyparhar393]

should I practice topics like DP on geeks for geeks list to learn the concepts or just do problems on platforms like cf and learn them gradually?

[@patrickdaniel2363]

It can be solved without extra space, just changing the original matrix if it's allowed.

[@TrickyCat]

Hi. What do you use for drawings (like the one in this video)?

[@hellowill]

What about maximal rectangle?

[@workhardplayhard0]

Hi, what if the question become area of largest rectangle, not square ? Is there a dp solution to that as well?

[@workhardplayhard0]

@Arif Rezai wow ok thanks mate

[@코연몬]

very useful

[@dpark-z4]

Thank you🤩

[@Chris_Lan]

What do you use to draw those explanation?

[@mohdekrama8597]

loved it💓

[@kolloktn]

Thanks

[@petrob123]

This is great

[@shashanktiwari4442]

When are u doing codejam training livestream?? Waiting for it :D

[@Errichto]

Sometime in May for sure!

[@PasselivreEdicoes]

I did 2d prefix sum with binary search, I think it's easier to come up with than DP, if you know 2d prefix sums

[@piyushnaithani7689]

What if ques says, find the maximal rectangle of 1s???

[@lovleshbhatt7797]

We just make an 2D array of data type pair and use dp , but at every point for the first element of pair i,e, dp[i][j].first = dp[i-1][j]+1; // consider for find the max length vertically similarly dp[i][j].second=dp[i][j-1]+1; // consider for finding the max length horizontally Note-: if at any point mat[i][j]=0, we initialise dp[i][j].first=0; dp[i][j].second=0; Also use a 2 varible max_x, max_y to store the max value of dp[i][j].first and dp[i][j].second at every instance of traversing

[@abdulsalamkhan1986]

What a coincidence, I too got same WA twice

[@oudarjatanmoy384]

best regards from me.. i want to know if i taka max(dp[i-1][j-1],dp[i-1][j],dp[i][j-1]) +1 it will work on maximum rectangle of one????

[@mahindrakatta2957]

what if the question asks the maximum rectangle possible?

[@mridulkumar786]

Guy who tried hard to understand dynamic programming but cannot get it, disliked this video

[@faridgadzhiev1440]

Great explanation as always. Are you going to cover May challenge as well? leetcode.com/explore/challenge/card/may-leetcoding-challenge/

[@c_tanki207]

No he told in his other live stream that he will be taking a break from leet code coz it bores him now... He will now go for topcoder an codeforces I presume

[@KumarShanoo]

what is the app u use for timer

[@lumigg2556]

This is the closest we can get of an IRL Neo

[@suvadeepghoshal]

Visit India once.. kamil and organize a camp. I want to meet you live !!! (Super excited)

[@sourabhkhandelwal1568]

Amrita University does regular training camps. When I participated in ICPC the teams there got invite for the training camp that was going to take place the next year. Codechef can make Kamil the guest invites of one such events. Back in college, I didn't have money to attend CP bootcamps but now cause of having a job I can afford them unless they are too costly. Will be looking forward to join if Errichto is really teaching something in them. :)

[@rajshekhar2953]

In a time of coronavirus pandemic, no one is allowed to do the live gathering. Who will be responsible, god forbid, for his misshapen?

[@suvadeepghoshal]

@@rajshekhar2953 not now.. -_- after this all cools down..

[@TanvirSojal]

@@suvadeepghoshal He visited India for IPC camp 2017. You can watch the videos here: kzbin.info/aero/PLi0ZM-RCX5nvImim3_ilsdLOtDDkOWt-X

[@sourabhkhandelwal1568]

@@TanvirSojal wow, thanks for this. Edit - Sound quality is too bad.

[@thatnaman]

It takes me 2 mins to read and understand what the question is asking for.

[@hemanthkotagiri8865]

I just don't understand anything about what you did there. How do I go about this? Please, can you suggest to me improve my competitive programming skills?

[@sangramjitchakraborty7845]

Read up on dynamic programming

[@jimmyshenmusic]

A similar problem in a recent leetcode contest. leetcode.com/problems/number-of-substrings-with-only-1s/

[@Heulitig117]

When you realise that his typing speed is faster than the speed you are probably thinking the solution.

[@rentib9136]

I hate dp. Give me a problem on finger tree

[@parthokunda]

I tried soving the problem but got 0 as answer whatever I tried. Finally, watching the video I found that values are characters, not integers :( . what a waste of time.

[@satyampatidar5848]

3×5 is not the square in red line

[@Errichto]

Did I claim otherwise? Timestamp please.

[@jameysiddiqui6910]

your face should be at bottom right corner and editor should be up

[@user-rz8lc3zl7k]

Hey brother do you read the Bible? Remember this life is only temporary

[@sankarraja5709]

An N*N matrix containing 1s and Os is given as the input to the program. The program must print the number of 2x2 unit matrices in the given matrix. A matrix is said to be unit matrix if all the integers are 1. Also, consider the overlapping matrices.