Find the Minimum Area to Cover All Ones I
Real-world version: The Smallest Crop Around the MarksThe statement here is our own: the same inputs, outputs and technique.
A scanned page is held as a grid of cells. sheet[i][j] is 1 when that cell carries a mark and 0 when it is blank, and at least one cell carries a mark.
You want to crop the page down to a rectangle of whole cells whose sides run along the rows and columns, keeping every marked cell inside the crop. Blank cells inside the crop are fine.
Return the smallest number of cells such a crop can hold.
Examples
Example 1
- Input
- sheet = [[1, 0], [0, 1]]
- Output
- 4
The two marks sit on different rows and different columns, so the crop has to span both rows and both columns and takes in all four cells.
Example 2
- Input
- sheet = [[0, 0, 0, 0], [0, 1, 1, 0], [0, 1, 0, 0], [0, 0, 0, 0]]
- Output
- 4
The marks occupy rows 1 and 2 and columns 1 and 2, so a two by two crop holds them. The blank cell it picks up in the corner costs nothing.
Example 3
- Input
- sheet = [[0, 1, 0, 0, 0]]
- Output
- 1
One mark on a single row, so the crop closes down to that one cell.
Constraints
- 1 <= sheet.length <= 1000
- 1 <= sheet[i].length <= 1000
- 0 <= sheet[i][j] <= 1
- at least one cell of sheet holds 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 minimum_area(sheet: list[list[int]]) -> int:public int minimumArea(int[][] sheet)Checking your plan…
How this problem was checked
- Passed: Reference solution run against 14 test cases: 14 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