Given a binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
Constraints:
rows matrix.length
cols matrix[i].length
rows, cols
matrix[i][j] is ‘0’ or ‘1’.
The problem asks us to find the largest rectangle made entirely of ‘1’s in a 2D binary matrix. Instead of checking every possible rectangle, which would be extremely slow, we use a dynamic programming trick that turns each row into the base of a histogram.
As we scan each row, we keep track of how many consecutive ‘1’s appear vertically in each column. That gives us a histogram for the current row. If a cell contains a ‘1’, its height grows; otherwise, if it’s a ‘0’, the height resets.
Along with heights, we track how far each column can extend left and right without bumping into a ‘0’. These boundaries effectively indicate the widest possible rectangle that can be placed on top ...
Given a binary matrix filled with 0’s and 1’s, find the largest rectangle containing only 1’s and return its area.
Constraints:
rows matrix.length
cols matrix[i].length
rows, cols
matrix[i][j] is ‘0’ or ‘1’.
The problem asks us to find the largest rectangle made entirely of ‘1’s in a 2D binary matrix. Instead of checking every possible rectangle, which would be extremely slow, we use a dynamic programming trick that turns each row into the base of a histogram.
As we scan each row, we keep track of how many consecutive ‘1’s appear vertically in each column. That gives us a histogram for the current row. If a cell contains a ‘1’, its height grows; otherwise, if it’s a ‘0’, the height resets.
Along with heights, we track how far each column can extend left and right without bumping into a ‘0’. These boundaries effectively indicate the widest possible rectangle that can be placed on top ...