### 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?

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?

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.

ReplyDeleteDo you have a solution? please share.

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

ReplyDelete