Https://ide.codingblocks.com/s/218571 getting only 1 correct in all ones

#1

I am making a height matrix in which I am storing the no. of 1s above continuously above a given 1.

then I am starting form the 1st row and moving column by column in height mat.

if I encounter any non-zero value say 2 then this means that it has 2 ones continuously inluding itself above it.this means that if the next column in the same row contains a value>=2 then we can make a square of side 2,because the heights in two consecutive square is 2 therefore the square is possible.

But if the next column in the same row had not been a value>=2 then this means that square of side 2 is not possible from this box in this row.

my approach basically is that i will encounter a height and then i will check that if i can move forward height-1 times condition is that in every move the height of the current box should be >= the starting box.

if we are able to move then this shows that the square of height stored in starting box is possible.

i am doing this row by row and in the end printing the max value of such square.

#2

@Adarshrajpandey Let’s say we define dp[i][j] as size of largest square whose right most bottom corner is (i,j).We can see that dp[i][j] can be written as min(dp[i][j-1],dp[i-1][j-1],dp[i-1][j])+1 ojnly if (a[i][j]==1) Otherwise dp[i][j]=0;

#3

ma’am I m doing that by taking left corner of the squrare.
Can u please check where I m going wrong?

#4

@Adarshrajpandey please share your code

#5

https://ide.codingblocks.com/s/218571

#6

@Adarshrajpandey actually this logic is not same at all. You can start by any corner you want but the approach will be same. If you choose the min(dp[i][j-1],dp[i-1][j-1],dp[i-1][j])+1 each time it is quite simple. You are over-complicating the problem which might not cover all the cases.