1186MediumArrayMatrix

The Smallest Crop Around the Marks

Tracked in this browser only

Trains the technique from

LeetCode 3195Find the Minimum Area to Cover All Ones I

This is an original problem, written from a brief that listed the technique, the difficulty, the topics, the function shape and the input bounds — none of that problem's wording, examples, hints or editorials. The link is there so you can map your practice onto the standard set.

Same function shape, different story and different numbers.

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 is preloaded with this. It matches the parent problem's shape, so a solution that works here transfers to a judge unchanged.

Python

def minimum_area(sheet: list[list[int]]) -> int:

Java

public int minimumArea(int[][] sheet)

The intended approach

Time O(m * n) for the single sweep of the page.Space O(1) beyond the page itself.

A crop is fixed by four numbers: its first and last row and its first and last column. To hold the topmost mark it must start at or above that mark's row, and the same reasoning at the other three sides means the crop has to reach at least from the topmost marked row to the bottommost and from the leftmost marked column to the rightmost. That smallest allowed crop already works. Any marked cell sits on a row between the topmost and bottommost marked rows and on a column between the leftmost and rightmost marked columns, so it is inside. So the four extremes are both forced and enough, and one sweep of the page collecting them settles the answer as the number of rows spanned times the number of columns spanned. Remember to count the boundary rows and columns themselves, which is where the two `+ 1` terms come from.

Pythonentry point: minimum_area

def minimum_area(sheet):
    top = -1
    bottom = -1
    left = -1
    right = -1
    for r, row in enumerate(sheet):
        for c, cell in enumerate(row):
            if cell != 1:
                continue
            if top < 0:
                top = r
            bottom = r
            if left < 0 or c < left:
                left = c
            if right < 0 or c > right:
                right = c
    return (bottom - top + 1) * (right - left + 1)

The obvious version

Try every crop there is. Run over each choice of first and last row and each choice of first and last column, check that no marked cell falls outside the four sides, and keep the smallest cell count among the crops that pass. Costs a pass over the page for each of the quadratically many crops.

This is not filler. It was written independently of the fast solution and the two were run against thousands of random inputs to confirm they agree — which is how the answer above is known to be right. Read it when the intended approach feels like a rabbit pulled out of a hat.

Python

def bf_minimum_area(sheet):
    rows = len(sheet)
    cols = len(sheet[0])
    best = -1
    for top in range(rows):
        for bottom in range(top, rows):
            for left in range(cols):
                for right in range(left, cols):
                    fits = True
                    for r in range(rows):
                        for c in range(cols):
                            if sheet[r][c] == 1 and (r < top or r > bottom or c < left or c > right):
                                fits = False
                                break
                        if not fits:
                            break
                    if fits:
                        area = (bottom - top + 1) * (right - left + 1)
                        if best < 0 or area < best:
                            best = area
    return best

How this problem was checked

Reference solution executed against 14 test cases — 14 passed
3 worked examples confirmed by running the code
0 eight-word sequences shared with the parent problem's text
Agrees with an independent brute-force implementation on random inputs
Test set proven to catch deliberately broken solutions
Reviewed by a separate quality pass
Function arity matches the parent problem's

Create a free account to unlock the solution

See the step-by-step animation, the intuition, and clean code in every language — free, no credit card.

Create a free account Already have an account? Sign in