Find the Largest Submatrix with all 1s

First clarify a crucial ambiguity: the classic maximal rectangle requires original column order, while a related problem allows rearranging columns independently for each row. In both cases, update heights[c] for each row: increment when matrix[r][c] is one, otherwise reset to zero. For fixed columns, run a monotonic increasing stack on the histogram; when a shorter bar arrives, pop bars and compute widths bounded by the current index and the new stack top. For rearrangeable columns, sort heights descending and test height[i] times i plus one. Explain the histogram invariant rather than memorizing code. Test all zeros, one row, one column, a full rectangle, and zeros breaking a tall column. The fixed-order stack approach is O(rowscols) time and O(cols) space; sorting per row is O(rowscols log cols) time and O(cols) space.