Count Square Submatrices with All Ones | Dynamic Programming | Rolling Hash | Leetcode

This video explains a very important programming interview problem which is to count the number of square sub matrices which are having all ones. This can be solved using many approaches. I have explained 2 approaches for this problem. The first method is by using Rolling Hash algorithm and the second method is the most optimal approach using dynamic programming. I have explained every intuition required to solve this problem step by step so that you can understand all the steps involved while using dynamic programming.At the end of the video i have explained the CODE walkthrough. CODE LINK is present below as usual. 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 :)
LinkedIn: / surya-pratap-kahar-47b... LINK: gist.github.co...
SIMILAR PROBLEMS:-
Rolling HASH: • Rolling hash | Rabin k...
Maximal Square: • Maximal square | Dynam...

[@ayeshaadhikari6123]

Thanks a lot sir! I was about to stop the video and skip this question but then you said - " you might not understand now, keep following the video, you'll understand" and this was a perfect push! I did understand the solution after the first 15 minutes. Great thanks to you and your efforts!

[@vishnukumavat7489]

I never observed the patterns the way you did. It is such a great observation pattern you followed here. Thanks a lot for this.

[@techdose4u]

Welcome

[@agileprogramming7463]

I cannot believe that this kind of content is for free!! Too good to be true

[@techdose4u]

😅

[@agileprogramming7463]

@@techdose4u Sir you are great.

[@infinitibucket]

Who cannot understand this after you have explained it so crisp and clear!

[@hasrat17]

beautiful solution ... And well explained

[@manishsalvi2901]

You put so much effort to make us understand. Learn a lot from you. Thanks 😊

[@techdose4u]

Welcome :)

[@amitupadhyay6511]

Wow, I thought this will be pretty tough one, tried for like 45 mins but no good. Thanks to your video, the trick is super-easy and coding is even easier lol

[@techdose4u]

Welcome 😀

[@yitingg7942]

Did it myself easily with O(1) space since I remembered you had a previous video about this square method. 😎😎

[@techdose4u]

Great ❤️

[@amitavamozumder73]

could u tell how to do that,i could only reduce space to 2xRow size :(

[@neerajpant4071]

It's always a good option to watch your videos than reading explanation in leetcode
It's good approach u focus more on explaination and approacg rather the coding👍

[@techdose4u]

Thanks :)

[@HimanshuKumar-xz5tk]

Wonderful, finally understood why we doing what we doing to solve this

[@crankyinmv]

Thanks for that. I wound up doing a variation which mapped total # of 1s in a rectangle between 0,0 and the each cell. A little more involved, but it worked.

[@techdose4u]

Nice.

[@AngadSingh97]

this was amazing, I had to see 2 other videos for this, but it was totally worth it.

[@techdose4u]

Thanks :)

[@vivektyson]

Best explanation on this problem. Amazing sir. I watched a lot of videos on this problem but couldn't understand it. Thank you so much sir.

[@techdose4u]

Welcome :)

[@parthshah6343]

I solved it using the method you suggested for Maximal Square problem in the exact same way!

[@techdose4u]

Nice :)

[@Amit_Kumar_1999]

Solved it with dp. But I will definitely try it with rolling hash today. Thanks for idea.

[@techdose4u]

👍

[@sonu-ou2hx]

The way you explain the problem along with its solution is amazing .
Thanks a lot Sir.

[@techdose4u]

Thanks :)

[@mohdfarman3470]

Sir your explanations are best ,please make more videos like these.

[@setYourHandleHttp404]

You provide the best way to convey the logic!

[@techdose4u]

Thanks :)

[@Bruner4]

I skipped first 2 for cycles and scrolled the whole matrix adding 1 in case, in this way:
if (matrix[i][j] == 1)
ausMat[i][j] = Math.min(ausMat[i - 1][j - 1], Math.min(ausMat[i - 1][j], ausMat[i][j - 1])) + 1;
Computationally speaking is the same thing I guess, right?
Btw amazing videos man, keep going!!

[@techdose4u]

Yes both are same.

[@spetsnaz_2]

I was able to get near the solution by using your concept explained in the problem Maximal Square. Using that I had the idea to take the min of all three sides + 1 😜
BTW this problem can also be solved in-place

[@techdose4u]

🤔

[@MohitBhagwani94]

Sir your explanation is awesome. There is nothing wrong in your code just one refinement.
We don't need an extra vector DP to store the value, we can change the matrix value in-place. My code is in java, please do let me know if it's wrong and what problem I'll face if I change the matrix value?
class Solution {
public int countSquares(int[][] matrix) {
int m = matrix.length;
int n = matrix[0].length;
int total=0;
for(int i=0;i0){
matrix[i][j] = Math.min(matrix[i-1][j],Math.min(matrix[i][j-1],matrix[i-1][j-1]))+1;
}
total +=matrix[i][j];
}
return total;
}
}
Thanks in advance.

[@techdose4u]

Yes you are correct.

[@rohithv63]

Great explanation and the idea helped me to code on my own. Very much helpful

[@techdose4u]

Nice :)

[@jameslin9845]

Very easy to understand. Thanks

[@techdose4u]

Welcome

[@soumilkhandelwal4388]

very nice... Usually, try to solve questions on my own... but couldn't get the logic even after 3 hours, Thanks for such a nice explanation. Now please tell how did you come up with this approach!! the thought process, because these type of questions usually goes in DFS or some graph-related stuff. How did you get to this solution buddy?

[@techdose4u]

I have done many such questions so din't wait to think on how to solve 😅

[@soumilkhandelwal4388]

@@techdose4u lol ... ohk ... Just wanted to know the thought process... In future whenever you solve a tricky question please provide your thought process... because that is the actual thing which really helps.

[@BaishaliGhosh13]

Your explanations are really great. Thank you for your help. Rolling Hash concept is really great and I have learnt it from your channel.

[@techdose4u]

Welcome :)

[@wentingsong9435]

Looking forward to your videos everyday, you gave me so much motivation, thanks!

[@techdose4u]

Woww... Welcome :)

[@luzengyuan5326]

very clear explanation. thanks

[@techdose4u]

Welcome :)

[@joseph2073]

thanku so much for the explanation man. u made it so easy. god bless u ! :)

[@shivamahuja840]

hi sir your all videos are the best sir can you please make videos on all types of questions of letter combination of phone like one with only recursion,then with backtracking and then with dp it will be a good topic for everyone and its not covered yet anywhere..

[@techdose4u]

I will try

[@mohammadyahya78]

Thank you. Can you please add more why we multiple by min(N,M) at 4:29?

[@amanbansal97]

8:40 I hope you didn't understand it too well 😂

[@techdose4u]

😅

[@noicebolte3920]

I hope he didn't hope that

[@undefined_exception_0]

Sir , instead of considering the matrix cell as bottom right corner of the square , can we consider it as top left corner and then start solving the problem from last cell to the first cell ?

[@kushgupta1187]

Thanks for taking time every day and uploading video.. Just a suggestion when explaining dp solution first share recursive equation otherwise we would not be to get how we reach to equation inside loop and every new question related to dp will become almost impossible for us to solve as we don't know how to form recursive equation.

[@techdose4u]

This is not a typical recursion question hence was difficult to solve using direct DP. I have already explained recursion formulation and its conversion to DP solution as well. I will do this in future as well. But this was not a typical recursive problem. So, I went with examples.

[@kushgupta1187]

Thanks for replying.. May be i am wrong but i think every dp has recursive equation. We just minimizes call by storing previous result in memory.
Thanks anyways for detail explanation of approach :)

[@deepaligarg2978]

Simply wonderful

[@nikhil_squats]

aap insaan nhi farishta ho, keep making these videos really helpful
please increase the frequency of making videos

[@papayasprout]

Thanks man. Very well explained

[@hemantsinghmanral8898]

Nice explanation...thanks for posting problems everyday

[@techdose4u]

Will continue everyday this month.

[@garumugam4480]

Nice explanation. I have to learn dynamic programming..

[@techdose4u]

Keep learning :)

[@christophermg1986]

Loved this Dose for dp :)

[@paragroy5359]

Too good explanation sir, i can't imagine getting all this for free..Thanks a lot sir

[@techdose4u]

Welcome :)

[@nurshuvo3854]

Great tutorial.

[@pranjalsharma499]

Very well Explained

[@ajaywadhwa3398]

Awesome Explanations !! Really helped alot.

[@techdose4u]

Thanks :)

[@rakshitsahu3417]

best explanation!

[@techdose4u]

Thanks :)

[@akshbansal7715]

If we do the operations in the original matrix itself then space complexity would be O(1), right?

[@techdose4u]

Yes correct. It can be done inplace.

[@aswathsrimarir2501]

How do we need to approach if they ask us not only to consider square matrices.? and count matrices of any dimensions?

[@avinabhchambial6283]

thanks man! you're a life saver :)

[@techdose4u]

Welcome :)

[@mohdfarhanahmed9416]

Can we get the java code as well in the upcoming videos?

[@ShubhamMahawar_Dancer_Actor]

Great man,you are really doing a great job

[@techdose4u]

Thanks :)

[@youtubealgorithm2128]

thanks a lot bro for this video

[@tushardhote6393]

Your explanation is amazing.. 👌🏻👌🏻👌🏻
Please upload explanation of leetCode problem "Surrounded regions". It will be appreciated 💯💯💯

[@techdose4u]

Will do more questions later bro.....feeling exhausted by putting video everyday :(

[@ds_world2468]

class Solution {

public void bfs(char[][] board, boolean visited[][], int rows, int cols, int i, int j){
if(i < 0 || i == rows || j < 0 || j == cols || visited[i][j] || board[i][j] != 'O')
return;
visited[i][j] = true;
bfs(board, visited, rows, cols, i-1, j);
bfs(board, visited, rows, cols, i+1, j);
bfs(board, visited, rows, cols, i, j-1);
bfs(board, visited, rows, cols, i, j+1);
}

public void solve(char[][] board) {
if(board.length == 0 || board[0].length == 0)
return;
int rows = board.length, cols = board[0].length;
boolean visited[][] = new boolean[rows][cols];

for(int c = 0; c < cols; c++){
if(board[0][c] == 'O')
bfs(board, visited, rows, cols, 0, c);
if(board[rows-1][c] == 'O')
bfs(board, visited, rows, cols, rows-1, c);
}
for(int r = 0; r < rows; r++){
if(board[r][0] == 'O')
bfs(board, visited, rows, cols, r, 0);
if(board[r][cols-1] == 'O')
bfs(board, visited, rows, cols, r, cols-1);
}

for(int i = 1; i < rows-1; i++){
for(int j = 1; j < cols-1; j++){
if(board[i][j] == 'O' && visited[i][j] == false)
board[i][j] = 'X';
}
}

}
}

[@thiyagarajanr225]

Such a great insight! Bro

[@techdose4u]

Thanks :)

[@siddhartha.saif25]

very nice! thanks!

[@techdose4u]

Welcome :)

[@siddhartha.saif25]

@@techdose4u the instructions are so very clear. there are lot of things to learn from you. thank you for all the great work you are doing.

[@fiascoDazzle]

Thanks for uploading great videos. Is there a way we can extend the 2nd method to calculate the count for submatrices of 1s in a matrix of 1 and 0?

[@hemantsinghmanral8898]

can you please add a playlist of questions based on graphs i find them very hard

[@techdose4u]

Sure will do that.

[@princeakhil208]

Can you please do a playlist on graph problems..

[@techdose4u]

Yes will do it as soon as leetcode challenges end.

[@gorakhkumargupta491]

Amazing content

[@algorithmimplementer415]

This channel rocks!!

[@techdose4u]

Thanks man :)

[@dovyraj1272]

sir u r great

[@techdose4u]

Thanks :)

[@desihiphop4998]

Dope solution man !!!!!!!!!!1

[@techdose4u]

Thanks ☺️

[@codingwithanonymous890]

Sir competitive nhi ho raha...can i be good software devloper?

[@HarshGupta-if2xg]

please upload problem on a daily basis.

[@techdose4u]

I am uploading on daily basis only from the last 2 months. I think you miss the videos. I will not continue on daily basis from next month onwards.

[@sumanthsaadam4522]

Problems on stacks and queues please

[@techdose4u]

Please check stack and queue playlist.

[@mohammadyahya78]

Can you please post the rolling hash 2d algorithm in Java?

[@techsquare6708]

awesome

[@techdose4u]

Welcome :)

[@ruchivora1190]

great explanation!

[@techdose4u]

Thanks

[@sammyali2938]

I tried to write the code. It did NOT work. I checked every thing, it does not work.

[@techdose4u]

Post your code in New comment on this video to get help.

[@cyruspassi457]

Your Linkedin says "This profile is not available".

[@techdose4u]

I will check it. Maybe the link is broken.

[@manjunathm3384]

Can please solve this code using python or c

[@techdose4u]

It is not possible for me but I can recommend you 2 things. 1st, you can get any language solution by just going to the leetcode problem discussions. 2nd, you can see if somebody has posted the code. I will soon create a repo where everyone can contribute and so it will be much easier.

[@manjunathm3384]

@@techdose4u thank you sir

[@ds_world2468]

First View... I had used the same approach...Nice Explanation

[@techdose4u]

👍 Thanks

[@b.sainathreddy4567]

this is same as maximal square leetcode problem

[@techdose4u]

Seems same

[@satanshuag]

in start i as : | ..... Till the end --> : )

[@symbol767]

Why do companies ask these ridiculous questions, holy hell..