We can use the Largest Rectangle in Histogram algorithm from leetcode 84, repeatedly over rows of column counts. This results in O(Rows * Cols) time and an extra O(Cols) space.
![](https://www.adamk.org/wp-content/uploads/2019/10/whiteboard-leetcode85-1024x768.jpg)
We can use the Largest Rectangle in Histogram algorithm from leetcode 84, repeatedly over rows of column counts. This results in O(Rows * Cols) time and an extra O(Cols) space.