Sub matrix

U are given a n*n square matrix where each element is either 0 or 1....u have to find the square submatrix with the largest length such that all the elements along the border of that square submatrix matrix is 1 ....

Questions by hari_nowayout   answers by hari_nowayout

Showing Answers 1 - 6 of 6 Answers

cyrano_says

  • Jul 26th, 2008
 

You go through one element at a time and figure out whats the maximum lenght along one side that has all 1's.
Eg starting with (1,1). Keep looking along the vertical. (1,2),(1,3)....
Once you hit a 0. save the length and walk downwards from the element.
(2,1),(3,1). If you find a shorter length or same length try to complete the square for that element and store the size. Repeat this for all elements and update the length when you hit a bigger square.

Give your answer:

If you think the above answer is not correct, Please select a reason and add your answer below.

 

Related Answered Questions

 

Related Open Questions