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