Largest Rectangle in a Matrix:

Given an n by n matrix with zeros and ones, find the largest sub- 
matrix full of ones in linear time.  I was told that a solution with 
O(n) time complexity exists. If there are n^2 elements in a n X n 
matrix how does a linear solution exist?


  1. is it possible to find the solution in linear time? there are n^2 elements ,even if you just traverse them, time complexity will be O(n^2) and we cannot say whether an element is 0 or 1 without reading it.

    Do you have a solution? please share.

  2. Usually it is said linear in the number of elements (there are n^2 elements). I think this is where the confusion comes from


Post a Comment

Popular posts from this blog