Three Rectangles Over the Ones

Hard

You are given a table grid of zeros and ones. Choose three rectangles with sides along the grid lines so that every cell holding a one lies inside one of them. The rectangles must not overlap (sharing a border is fine), and each must have an area of at least 1. Return the smallest possible total area of the three rectangles.

Example 1

grid=[[1, 1, 0], [0, 0, 1], [1, 0, 1]] → 5

A 1 × 2 rectangle over the two ones in the top row, a 1 × 1 over cell (2, 0) and a 2 × 1 over cells (1, 2) and (2, 2): 2 + 1 + 2 = 5.

Example 2

grid=[[1, 0, 0, 1], [0, 0, 0, 0], [0, 1, 0, 0]] → 3

Each of the three ones gets its own 1 × 1 square.

Constraints

1 ≤ len(grid), len(grid[i]) ≤ 30
grid[i][j] is 0 or 1
The table contains at least three ones

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Enumeration Matrix

Similar problems

Three Peaceful Rooks Hard Three Rooks on a Big Board Hard Flanking Move on the Board Medium A Word in a Crossword Slot Medium Columns That Cover Rows Medium

Input

grid=[[1, 1, 0], [0, 0, 1], [1, 0, 1]]

Expected

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