Largest Submatrix With Rearrangements
Real-world version: Widest Block After Reordering ColumnsThe statement here is our own: the same inputs, outputs and technique.
A punch card sheet is a grid of 0s and 1s given as matrix. The columns may be reordered freely, as often as you like, and reordering moves a whole column with all its entries.
A block is a rectangle of cells, taken from consecutive rows and consecutive columns of the reordered sheet, in which every cell is 1. Return the largest area a block can have, where area is the number of cells.
Examples
Example 1
- Input
- matrix = [[1, 0, 1], [1, 1, 0], [1, 0, 1], [1, 1, 1]]
- Output
- 4
The first column holds ones all the way down, giving a block one column wide and four rows tall, an area of 4.
Example 2
- Input
- matrix = [[1, 0], [0, 1]]
- Output
- 1
No two cells of ones share a row or a column band, so the largest block is a single cell.
Example 3
- Input
- matrix = [[1, 1, 1, 1]]
- Output
- 4
The single row is all ones, so the whole sheet is one block of area 4.
Constraints
- 1 <= matrix.length <= 10^5
- 1 <= matrix[0].length <= 10^5
- Every row of matrix has the same length, and the sheet holds at most 10^5 cells
- 0 <= matrix[i][j] <= 1
The signature
The editor starts with this. It matches the parent problem's shape, so a solution that works here works on a standard judge unchanged.
def widest_block(matrix: list[list[int]]) -> int:public int widestBlock(int[][] matrix)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 11 test cases: 11 passed
- Passed: 3 worked examples confirmed by running the code
- Passed: 0 eight-word sequences shared with the parent problem's text
- Passed: Agrees with an independent brute-force solution on random inputs
- Passed: Test set shown to catch deliberately broken solutions
- Passed: Reviewed by a separate quality pass
- Passed: Function arity matches the parent problem's