FastPrepMinimum Boards to Cover Roof Holes

Minimum Boards to Cover Roof Holes

Google logoGoogle● HardNEW GRADPHONE SCREEN
Learn

Problem statement

An m x n binary matrix roof describes a roof. A cell containing 0 is a hole, while a cell containing 1 is intact.

You may place either kind of board:

  • A horizontal 1 x n board covers every cell in one chosen row.
  • A vertical m x 1 board covers every cell in one chosen column.

Boards may overlap. Return the minimum number of boards needed so every hole is covered.

Function

minimumRoofBoards(roof: int[][]) → int

Examples

Example 1

roof = [[1,0,1],[0,1,0]]return = 2

Cover row 1 and column 1. Together they cover all three holes.

Example 2

roof = [[1,1],[1,1]]return = 0

An intact roof needs no board.

Example 3

roof = [[0,0,0],[0,0,0]]return = 2

Two horizontal boards cover the complete roof, which is fewer than the three vertical boards.

Constraints

  • 1 <= m, n <= 300.
  • Every row has exactly n cells.
  • Every cell is 0 or 1.

More Google problems

See Google hiring insights
public int minimumRoofBoards(int[][] roof) {
    // write your code here
}
roof[[1,0,1],[0,1,0]]
expected2
Checking account…