Hii Mik, one thing that I want to tell you is that I started watching your channel because no one else was teaching brute force solution. Everyone was like do brute force solution by your own, and now let's jump to the optmised solution, but you were the only one who told that brute force is also necessary so I just love your content from that day it was gas station problem I still remember. My point of telling this story is always code brute force too and please dry run your code like older videos, that is your usp. Please, it's my humble request, and thank you for the amazing concept. loved your graph's concept playlist.
00:03 Count Square Submatrices with All Ones 00:56 Count the number of square submatrices with all ones in a given matrix. 02:41 Creating square submatrices with all ones using recursion 03:25 Explaining the process of counting square submatrices with all ones. 04:55 Observing diagonal movement and bottom-right direction is important. 05:42 Counting the number of submatrices with all ones 07:17 Identifying minimum square matrix size 08:09 Identify minimum square matrices with all ones 09:42 Determine the minimum number of squares that can be formed with given sides. 10:37 Count square submatrices with all ones 12:18 Identifying square submatrices formation in the matrix 13:12 Explaining grid traversal for right-hand side and diagonal movements 14:51 Understanding the formation of square submatrices. 15:45 Calculating the total number of square submatrices with all ones 17:17 Count square submatrices with all ones 18:24 Understand matrix traversal limitations and boundaries 20:20 Understanding the time complexity of the solution 21:16 Implement memoization using vector of vector of int in recursion 23:10 Explaining the bottom-up approach and its significance in recursion and dynamic programming. 23:54 Implementing recursion and memorization techniques in coding 26:01 Find answer for calculating submatrices with all ones 26:48 Understanding the approach to count square submatrices with all ones 29:14 Understanding and using the same equation in a Leetcode problem 30:06 Implementing bottom-up approach for counting square submatrices with all ones. 32:19 Count square submatrices with all ones using bottom up approach 33:07 Exploring the count of valid square matrices with ones and zeros. 34:46 Count square submatrices with all ones 35:33 Identifying minimum value of submatrices on diagonals and left side 37:06 Understanding and solving maximum square submatrices problem. 37:46 Identifying and including square submatrices with all ones based on cell values 39:53 Understanding the conditions for creating square submatrices with all ones 40:37 Implementing the algorithm for counting square submatrices with all ones efficiently
firstafall thankyou so much bhaiya your dp and graph series is really really amazing finished it in my 2nd year only and also DSA mid sem awesome gya because of you amazing work bhaiya really !!!
Love Your Videos Very Much MIK , Actually I Want To Know That Can I Get Internship Only By Mastering DSA At Goldman Sachs ? ( I Am Currently In My Second Year in Amity University Noida)
agar goldman sachs jana hai to aptitude ki prep karlena first round vahi hota hai 99 percent log nikal jate hai usme se hi even dsa ata ho to bhi i was one of them so dont take it lightly
//Bruteforce Approach class Solution { public int countSquares(int[][] matrix) { int totalSquareCount = 0; for (int row = 0; row < matrix.length; row++) { for (int col = 0; col < matrix[0].length; col++) { if (matrix[row][col] == 1) { totalSquareCount += countSquaresFromCell(matrix, row, col); } } } return totalSquareCount; } /* * It explores the longest stretch of 1's in three directions (right, diagonal down-right, and down) * and determines the maximum possible square size that includes the current cell as the top-left corner. */ private int countSquaresFromCell(int[][] matrix, int row, int col) { // Base case: If we go out of bounds, return 0 if (row == matrix.length || col == matrix[0].length) { return 0; } // If the current cell is 0, it cannot contribute to any square submatrices starting from this position if (matrix[row][col] == 0) { return 0; } // Recursively count 1's in three directions int rightCount = countSquaresFromCell(matrix, row, col + 1); // Count to the right int diagonalCount = countSquaresFromCell(matrix, row + 1, col + 1); // Count diagonally down-right int downCount = countSquaresFromCell(matrix, row + 1, col); // Count downwards /* * The total number of square submatrices that include the current cell as the top-left corner * (The 1 accounts for the smallest square of size 1x1 formed by the current cell itself) */ return 1 + Math.min(rightCount, Math.min(diagonalCount, downCount)); } } //Improved Approach class Solution { private int[][] cache; public int countSquares(int[][] matrix) { cache = new int[matrix.length][matrix[0].length]; intializeCache(); int totalSquareCount = 0; for (int row = 0; row < matrix.length; row++) { for (int col = 0; col < matrix[0].length; col++) { if (matrix[row][col] == 1) { totalSquareCount += countSquaresFromCell(matrix, row, col); } } } return totalSquareCount; } private int countSquaresFromCell(int[][] matrix, int row, int col) { if (row == matrix.length || col == matrix[0].length) { return 0; } if (matrix[row][col] == 0) { return 0; } if (cache[row][col] != -1) { return cache[row][col]; } int rightCount = countSquaresFromCell(matrix, row, col + 1); int diagonalCount = countSquaresFromCell(matrix, row + 1, col + 1); int downCount = countSquaresFromCell(matrix, row + 1, col); return cache[row][col] = 1 + Math.min(rightCount, Math.min(diagonalCount, downCount)); } private void intializeCache() { for (int i = 0; i < cache.length; i++) { Arrays.fill(cache[i], -1); } } } //Optimal Approach //Naive Implementation class Solution { public int countSquares(int[][] matrix) { /* * dp[i][j] represents the side length of the largest square submatrix whose * bottom-right corner is at (i, j), and also represents the total count of all * square submatrices that can end at that position (since squares can be of * sizes 1x1, 2x2, ..., up to the largest square that ends at (i, j)). */ int[][] dp = new int[matrix.length + 1][matrix[0].length + 1]; int totalSquareCount = 0; dp[matrix.length][matrix[0].length] = 0; for (int col = 0; col < matrix[0].length; col++) { dp[matrix.length][col] = 0; } for (int row = 0; row < matrix.length; row++) { dp[row][matrix[0].length] = 0; } for (int row = matrix.length - 1; row >= 0; row--) { for (int col = matrix[0].length - 1; col >= 0; col--) { if (matrix[row][col] == 1) { int rightCount = dp[row][col + 1]; int diagonalCount = dp[row + 1][col + 1]; int downCount = dp[row + 1][col]; dp[row][col] = 1 + Math.min(rightCount, Math.min(diagonalCount, downCount)); totalSquareCount += dp[row][col]; } else { dp[row][col] = 0; } } } return totalSquareCount; } } //Optimal Implementation class Solution { public int countSquares(int[][] matrix) { int[][] dp = new int[matrix.length + 1][matrix[0].length + 1]; int totalSquareCount = 0; for (int row = matrix.length - 1; row >= 0; row--) { for (int col = matrix[0].length - 1; col >= 0; col--) { if (matrix[row][col] == 1) { dp[row][col] = 1 + Math.min(dp[row][col + 1], Math.min(dp[row + 1][col + 1], dp[row + 1][col])); totalSquareCount += dp[row][col]; } } } return totalSquareCount; } } //Aliter (Space optimised) class Solution { public int countSquares(int[][] matrix) { int totalSquareCount = 0; int[] currrentRow = new int[matrix[0].length + 1]; int[] nextRow = new int[matrix[0].length + 1]; for (int row = matrix.length - 1; row >= 0; row--) { for (int col = matrix[0].length - 1; col >= 0; col--) { if (matrix[row][col] == 1) { currrentRow[col] = 1 + Math.min(currrentRow[col + 1], Math.min(nextRow[col + 1], nextRow[col])); totalSquareCount += currrentRow[col]; } else { currrentRow[col] = 0; } } int[] temp = currrentRow; currrentRow = nextRow; nextRow = temp; } return totalSquareCount; } } //Utilising the given question matrix space class Solution { public int countSquares(int[][] matrix) { int totalSquareCount = 0; for (int row = matrix.length - 1; row >= 0; row--) { for (int col = matrix[0].length - 1; col >= 0; col--) { if (matrix[row][col] == 1) { if (row == matrix.length - 1 || col == matrix[0].length - 1) { matrix[row][col] = 1; } else { matrix[row][col] = 1 + Math.min(matrix[row][col + 1], Math.min(matrix[row + 1][col + 1], matrix[row + 1][col])); } totalSquareCount += matrix[row][col]; } } } return totalSquareCount; } }
For memoizing, always notice how many variables are changing when calling solve function. Notice here two variables are changing i and j This means that for uniquely identifying a state, you need two variables, hence i took a 2D array to memoize them.
if we take a matrix 1 1 1 1 1 0 1 0 1 here the right 1s are 3 diag 1s are 3 and down 1s are also 3, so according to ur explaination it should be 1 + min(2,2,2) = 3, but the real ans for first 1 should be just 2 not 3, ik the recursion is beign called in all the directions for each and every cell, did i miss out something in the explanation? please help thanks
Suppose you are at (0,0), When you call the recursion for right, it will go to (0,1) where again same thing will be checked right, diagonal, below (note here minimum will be 0) And again recursion will be called to (0,2) where it will check right, diagonal, below. Think of like this and you Will Understand then ♥️
please explain the case for 1 1 1 1 1 0 1 1 1 if it is startting from the first one then it will give 3 size of square matrix is it checking for the 0 value
sir me hamesa bad fill karata kyoki main daily question nahi kar pata hu mujhe 1 year ho gya problem solve karte but i can not solve daily problem and if i watch video i fill bad because anyone can solve question after watching video but one thing is good which is you teaching style you teach well please tell me what should i do
Try to solve problems on your own don't just give up on any problem try try try try . There are people who continue to solve a problem for straight 3 hrs ? Did you do it ..? Question urself why are u lacking
leetcode 221 soln exact same h bs max aur square krna h class Solution { public: int maximalSquare(vector& matrix) { int m = matrix.size(); int n = matrix[0].size(); vector dp(m, vector(n, 0)); int result = 0; for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (i == 0 || j == 0) { dp[i][j] = matrix[i][j] - '0'; } else if (matrix[i][j] == '1') { dp[i][j] = 1 + min({dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]}); } result = max(result, dp[i][j]); } } return result * result; } };
why need dp. Simple code without dp. public int countSquares(int[][]matrix){ if(matrix.length==0) return 0; int m=matrix.length,n=matrix[0].length; for(int i=1;i
mik bhaiya apka video bina like kie khatam hi nhi hota harr bar maza aa jata h
Hii Mik, one thing that I want to tell you is that I started watching your channel because no one else was teaching brute force solution. Everyone was like do brute force solution by your own, and now let's jump to the optmised solution, but you were the only one who told that brute force is also necessary so I just love your content from that day it was gas station problem I still remember. My point of telling this story is always code brute force too and please dry run your code like older videos, that is your usp. Please, it's my humble request, and thank you for the amazing concept. loved your graph's concept playlist.
Thank you for mentioning this.
Point taken and I will definitely take care of this thing ♥️
@@codestorywithMIK Thank you so much ❤️
00:03 Count Square Submatrices with All Ones
00:56 Count the number of square submatrices with all ones in a given matrix.
02:41 Creating square submatrices with all ones using recursion
03:25 Explaining the process of counting square submatrices with all ones.
04:55 Observing diagonal movement and bottom-right direction is important.
05:42 Counting the number of submatrices with all ones
07:17 Identifying minimum square matrix size
08:09 Identify minimum square matrices with all ones
09:42 Determine the minimum number of squares that can be formed with given sides.
10:37 Count square submatrices with all ones
12:18 Identifying square submatrices formation in the matrix
13:12 Explaining grid traversal for right-hand side and diagonal movements
14:51 Understanding the formation of square submatrices.
15:45 Calculating the total number of square submatrices with all ones
17:17 Count square submatrices with all ones
18:24 Understand matrix traversal limitations and boundaries
20:20 Understanding the time complexity of the solution
21:16 Implement memoization using vector of vector of int in recursion
23:10 Explaining the bottom-up approach and its significance in recursion and dynamic programming.
23:54 Implementing recursion and memorization techniques in coding
26:01 Find answer for calculating submatrices with all ones
26:48 Understanding the approach to count square submatrices with all ones
29:14 Understanding and using the same equation in a Leetcode problem
30:06 Implementing bottom-up approach for counting square submatrices with all ones.
32:19 Count square submatrices with all ones using bottom up approach
33:07 Exploring the count of valid square matrices with ones and zeros.
34:46 Count square submatrices with all ones
35:33 Identifying minimum value of submatrices on diagonals and left side
37:06 Understanding and solving maximum square submatrices problem.
37:46 Identifying and including square submatrices with all ones based on cell values
39:53 Understanding the conditions for creating square submatrices with all ones
40:37 Implementing the algorithm for counting square submatrices with all ones efficiently
Thanks MIK . I was able to solve on my own.
bhai OP bhai very good thought process
Thanks for covering all details. All clear
Thank you so much Bhaiya ji 🙏🙏🙏
Thank you very much sir!!!
You’re welcome! ❤️🙏😇
Maja aa gya bhaiya
Thank you so much 😄
firstafall thankyou so much bhaiya your dp and graph series is really really amazing finished it in my 2nd year only and also DSA mid sem awesome gya because of you amazing work bhaiya really !!!
Love Your Videos Very Much MIK , Actually I Want To Know That Can I Get Internship Only By Mastering DSA At Goldman Sachs ? ( I Am Currently In My Second Year in Amity University Noida)
Agar fresher ho to DSA and college subjects - OS, DBMS etc will definitely help you get an internship
@@gui-codes thanks for your kind reply !
Yes
agar goldman sachs jana hai to aptitude ki prep karlena first round vahi hota hai 99 percent log nikal jate hai usme se hi even dsa ata ho to bhi i was one of them so dont take it lightly
@@batuklal same huwa bhai
Thanks 😊
ty :)
thanks...
Bhaiya, please update the DSA sheet when you get some free time. Thank u for the explanation ❤❤
Sure ♥️
Need to catch a flight tonight. Let me then work on it after that
@@codestorywithMIK ya thanks a lot the reply bhaiya . Happy journey stay safe and healthy ❤️❤️
No need to change recurrence relation just change the loop directions
Yep that will work too ♥️
@@codestorywithMIK thanks sir big fan
So should we start the loop from I=m-1 and j=n-1?
@@sidhant_369 yes if dp size is m+1,n+1
Bhaiys is space optimization further possible using a single row?
Leetcode contest ka solution provide karo na bhaiya😅😅
Will plan soon this week. Need to catch a flight tonight ♥️
@@codestorywithMIK happy journey✈️ bhaiya thanks alot
//Bruteforce Approach
class Solution {
public int countSquares(int[][] matrix) {
int totalSquareCount = 0;
for (int row = 0; row < matrix.length; row++) {
for (int col = 0; col < matrix[0].length; col++) {
if (matrix[row][col] == 1) {
totalSquareCount += countSquaresFromCell(matrix, row, col);
}
}
}
return totalSquareCount;
}
/*
* It explores the longest stretch of 1's in three directions (right, diagonal down-right, and down)
* and determines the maximum possible square size that includes the current cell as the top-left corner.
*/
private int countSquaresFromCell(int[][] matrix, int row, int col) {
// Base case: If we go out of bounds, return 0
if (row == matrix.length || col == matrix[0].length) {
return 0;
}
// If the current cell is 0, it cannot contribute to any square submatrices starting from this position
if (matrix[row][col] == 0) {
return 0;
}
// Recursively count 1's in three directions
int rightCount = countSquaresFromCell(matrix, row, col + 1); // Count to the right
int diagonalCount = countSquaresFromCell(matrix, row + 1, col + 1); // Count diagonally down-right
int downCount = countSquaresFromCell(matrix, row + 1, col); // Count downwards
/*
* The total number of square submatrices that include the current cell as the top-left corner
* (The 1 accounts for the smallest square of size 1x1 formed by the current cell itself)
*/
return 1 + Math.min(rightCount, Math.min(diagonalCount, downCount));
}
}
//Improved Approach
class Solution {
private int[][] cache;
public int countSquares(int[][] matrix) {
cache = new int[matrix.length][matrix[0].length];
intializeCache();
int totalSquareCount = 0;
for (int row = 0; row < matrix.length; row++) {
for (int col = 0; col < matrix[0].length; col++) {
if (matrix[row][col] == 1) {
totalSquareCount += countSquaresFromCell(matrix, row, col);
}
}
}
return totalSquareCount;
}
private int countSquaresFromCell(int[][] matrix, int row, int col) {
if (row == matrix.length || col == matrix[0].length) {
return 0;
}
if (matrix[row][col] == 0) {
return 0;
}
if (cache[row][col] != -1) {
return cache[row][col];
}
int rightCount = countSquaresFromCell(matrix, row, col + 1);
int diagonalCount = countSquaresFromCell(matrix, row + 1, col + 1);
int downCount = countSquaresFromCell(matrix, row + 1, col);
return cache[row][col] = 1 + Math.min(rightCount, Math.min(diagonalCount, downCount));
}
private void intializeCache() {
for (int i = 0; i < cache.length; i++) {
Arrays.fill(cache[i], -1);
}
}
}
//Optimal Approach
//Naive Implementation
class Solution {
public int countSquares(int[][] matrix) {
/*
* dp[i][j] represents the side length of the largest square submatrix whose
* bottom-right corner is at (i, j), and also represents the total count of all
* square submatrices that can end at that position (since squares can be of
* sizes 1x1, 2x2, ..., up to the largest square that ends at (i, j)).
*/
int[][] dp = new int[matrix.length + 1][matrix[0].length + 1];
int totalSquareCount = 0;
dp[matrix.length][matrix[0].length] = 0;
for (int col = 0; col < matrix[0].length; col++) {
dp[matrix.length][col] = 0;
}
for (int row = 0; row < matrix.length; row++) {
dp[row][matrix[0].length] = 0;
}
for (int row = matrix.length - 1; row >= 0; row--) {
for (int col = matrix[0].length - 1; col >= 0; col--) {
if (matrix[row][col] == 1) {
int rightCount = dp[row][col + 1];
int diagonalCount = dp[row + 1][col + 1];
int downCount = dp[row + 1][col];
dp[row][col] = 1 + Math.min(rightCount, Math.min(diagonalCount, downCount));
totalSquareCount += dp[row][col];
} else {
dp[row][col] = 0;
}
}
}
return totalSquareCount;
}
}
//Optimal Implementation
class Solution {
public int countSquares(int[][] matrix) {
int[][] dp = new int[matrix.length + 1][matrix[0].length + 1];
int totalSquareCount = 0;
for (int row = matrix.length - 1; row >= 0; row--) {
for (int col = matrix[0].length - 1; col >= 0; col--) {
if (matrix[row][col] == 1) {
dp[row][col] = 1 + Math.min(dp[row][col + 1], Math.min(dp[row + 1][col + 1], dp[row + 1][col]));
totalSquareCount += dp[row][col];
}
}
}
return totalSquareCount;
}
}
//Aliter (Space optimised)
class Solution {
public int countSquares(int[][] matrix) {
int totalSquareCount = 0;
int[] currrentRow = new int[matrix[0].length + 1];
int[] nextRow = new int[matrix[0].length + 1];
for (int row = matrix.length - 1; row >= 0; row--) {
for (int col = matrix[0].length - 1; col >= 0; col--) {
if (matrix[row][col] == 1) {
currrentRow[col] = 1 + Math.min(currrentRow[col + 1], Math.min(nextRow[col + 1], nextRow[col]));
totalSquareCount += currrentRow[col];
} else {
currrentRow[col] = 0;
}
}
int[] temp = currrentRow;
currrentRow = nextRow;
nextRow = temp;
}
return totalSquareCount;
}
}
//Utilising the given question matrix space
class Solution {
public int countSquares(int[][] matrix) {
int totalSquareCount = 0;
for (int row = matrix.length - 1; row >= 0; row--) {
for (int col = matrix[0].length - 1; col >= 0; col--) {
if (matrix[row][col] == 1) {
if (row == matrix.length - 1 || col == matrix[0].length - 1) {
matrix[row][col] = 1;
} else {
matrix[row][col] = 1 + Math.min(matrix[row][col + 1], Math.min(matrix[row + 1][col + 1], matrix[row + 1][col]));
}
totalSquareCount += matrix[row][col];
}
}
}
return totalSquareCount;
}
}
if cell(2,1) and cell(1,2) is 1 then how to analyse ?
Here is my code
class Solution {
public:
int countSquares(vector& mat) {
int n = mat.size();
int m = mat[0].size();
int res = 0;
for (int i = n - 1; i >= 0; i--)
{
for (int j = m - 1; j >= 0; j--)
{
if(i == n-1 || j == m-1){
res += mat[i][j];
continue;
}
if(mat[i][j] == 0){
continue;
}
mat[i][j] += min(mat[i][j+1], min(mat[i+1][j], mat[i+1][j+1]));
res += mat[i][j];
}
}
return res;
}
};
#within one min solved (timestamp 29:35 / 42:00)
Awesome 👍🏻
@@codestorywithMIK life would become more easier if you could make vdo on sql queries
hi understood everything except the memorization thing ,
can anyone explain why we created the t 2d matrix for memorization
For memoizing, always notice how many variables are changing when calling solve function.
Notice here two variables are changing i and j
This means that for uniquely identifying a state, you need two variables, hence i took a 2D array to memoize them.
if we take a matrix
1 1 1
1 1 0
1 0 1
here the right 1s are 3 diag 1s are 3 and down 1s are also 3, so according to ur explaination it should be 1 + min(2,2,2) = 3,
but the real ans for first 1 should be just 2 not 3, ik the recursion is beign called in all the directions for each and every cell,
did i miss out something in the explanation? please help thanks
Suppose you are at (0,0), When you call the recursion for right, it will go to
(0,1) where again same thing will be checked right, diagonal, below (note here minimum will be 0)
And again recursion will be called to (0,2) where it will check right, diagonal, below.
Think of like this and you Will Understand then ♥️
DONE THE TABULATION APPROACH MYSELF:
int countSquares(vector& matrix) {
// writing my own tabulation code
int m=matrix.size();
int n=matrix[0].size();
vectordp(m+1, vector(n+1,0));
int ans=0;
for(int i=m-1; i>=0; i--)
{
for(int j=n-1; j>=0; j--)
{
if(matrix[i][j]==0) dp[i][j]=0;
else{
dp[i][j]=1+min(dp[i+1][j], min(dp[i][j+1],dp[i+1][j+1]));
ans+=dp[i][j];
}
}
}
return ans;
}
Great ♥️
no need for dp[i][j]=0 cuz u already initialise it with 0
@@drashysesodia512 ya I should probably written continue
please explain the case for
1 1 1
1 1 0
1 1 1
if it is startting from the first one then it will give 3 size of square matrix
is it checking for the 0 value
If you notice, recursively every cell checks for 0.
Try to make recursion call diagram on paper, it will help you realise it easily ♥️
sir me hamesa bad fill karata kyoki main daily question nahi kar pata hu mujhe 1 year ho gya problem solve karte but i can not solve daily problem and if i watch video i fill bad because anyone can solve question after watching video but one thing is good which is you teaching style you teach well please tell me what should i do
Try to solve problems on your own don't just give up on any problem try try try try . There are people who continue to solve a problem for straight 3 hrs ? Did you do it ..? Question urself why are u lacking
Please leetcode context ke questions ka bhi solutions bata dijiye
Will plan soon this week. Need to catch a flight tonight ♥️
@@codestorywithMIK I am waiting thanks bro
@@codestorywithMIK sir do only the last problems of the contest no need to do all
if possible
happy journey btw
leetcode 221 soln exact same h bs max aur square krna h
class Solution {
public:
int maximalSquare(vector& matrix) {
int m = matrix.size();
int n = matrix[0].size();
vector dp(m, vector(n, 0));
int result = 0;
for (int i = 0; i < m; i++) {
for (int j = 0; j < n; j++) {
if (i == 0 || j == 0) {
dp[i][j] = matrix[i][j] - '0';
} else if (matrix[i][j] == '1') {
dp[i][j] =
1 + min({dp[i - 1][j], dp[i - 1][j - 1], dp[i][j - 1]});
}
result = max(result, dp[i][j]);
}
}
return result * result;
}
};
Indeed 🙌
First
why need dp. Simple code without dp.
public int countSquares(int[][]matrix){
if(matrix.length==0) return 0;
int m=matrix.length,n=matrix[0].length;
for(int i=1;i
Yep definitely , we can get rid of dp vector but will have to modify the input ♥️