Frame Around an Ink Blot

Hard

A sheet of paper is a grid sheet with m rows and n columns: "1" is an inked cell and "0" is a clean one. All inked cells form a single blot: you can get from any inked cell to any other by stepping up, down, left or right over inked cells. You know one cell of the blot, (row, col). Return the area of the smallest rectangle aligned with the rows and columns that covers the whole blot. Scanning every cell is the obvious way; try to beat O(m · n).

Example 1

sheet=[["0", "1", "1"], ["0", "1", "0"], ["1", "1", "0"]], row=0, col=1 → 9

The blot spans rows 0 to 2 and columns 0 to 2, so the frame is 3 × 3 = 9.

Example 2

sheet=[["0", "0", "0"], ["0", "1", "1"]], row=1, col=2 → 2

The blot is two cells in a single row, a 1 × 2 frame.

Example 3

sheet=[["1"]], row=0, col=0 → 1

Constraints

1 ≤ m, n ≤ 100
Each cell is "0" or "1"
0 ≤ row < m, 0 ≤ col < n, and sheet[row][col] = "1"
The inked cells form one connected region

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Depth-First Search Breadth-First Search Array Binary Search Matrix

Similar problems

Crossing at High Tide Hard Last Dry Crossing Day Hard Route With the Highest Bottleneck Medium The Gentlest Climb Medium Longest Uphill Walk Hard

Input

sheet=[["0", "1", "1"], ["0", "1", "0"], ["1", "1", "0"]], row=0, col=1

Expected

Run checks the first 3 tests in your browser. Submit checks all 47 tests on the server, hidden ones included.