Smallest Frame Around the Ones

Medium

You get a grid field of 0s and 1s with at least one 1 in it. All the 1s must be enclosed by a single rectangular frame whose sides run along the grid's rows and columns. Return the smallest possible area of such a frame, counted in cells.

Example 1

field=[[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1]] → 6

The 1s sit in rows 1–2 and columns 1–3: a 2 × 3 frame with area 6.

Example 2

field=[[1]] → 1

A single cell, area 1.

Example 3

field=[[0, 1], [0, 1], [0, 0]] → 2

Both 1s are in column 1: a 2 × 1 frame.

Constraints

1 ≤ rows, columns ≤ 1000
field[i][j] is 0 or 1
The grid has at least one 1

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Matrix

Similar problems

Sudoku Board Without Clashes Medium Turn a Square Clockwise Medium Spiral Readout Medium Spiral-Numbered Square Medium Warehouse Cart Routes Medium

Input

field=[[0, 0, 0, 0], [0, 1, 0, 0], [0, 0, 0, 1]]

Expected

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