Largest contiguous submatrix of "true" elements
This is an interview question: given a boolean matrix find the size of the largest contiguous square sub-matrix, which contains only "true" elements.

I found this [question][1] on SO but did not understand the answer. The proposed algorithm moves a diagonal line from the left top to the right bottom and keeps track of the rectangles of "true" elements as the line goes.

My questions;

- How to keep track of the rectangles?
- Why do we move the _diagonal_ line? What if we move a vertical/horizontal line or both?
- How to calculate the algorithm complexity? 



  [1]: http://stackoverflow.com/questions/4482408/find-the-largest-sub-matrix-full-of-ones-in-linear-time
Largest contiguous submatrix of "true" elements
===

This is an interview question: given a boolean matrix find the size of the largest contiguous square sub-matrix, which contains only "true" elements.

I found this [question][1] on SO but did not understand the answer. The proposed algorithm moves a diagonal line from the left top to the right bottom and keeps track of the rectangles of "true" elements as the line goes.

My questions;

- How to keep track of the rectangles?
- Why do we move the _diagonal_ line? What if we move a vertical/horizontal line or both?
- How to calculate the algorithm complexity? 



  [1]: http://stackoverflow.com/questions/4482408/find-the-largest-sub-matrix-full-of-ones-in-linear-time