FastPrepBounds of Every Zero Rectangle

Bounds of Every Zero Rectangle

Indeed logoIndeed● MediumFULLTIMEPHONE SCREEN
Learn

Problem statement

Given a nonempty rectangular integer matrix matrix containing only 0 and 1, return the bounds of every zero rectangle.

For this exercise, assume every group of zeros connected through immediately adjacent up, down, left or right cells is a completely filled axis-aligned rectangle. Separate rectangles never touch along an edge; they may touch diagonally. There may be no zero rectangle. Arbitrary shapes and overlapping rectangle decompositions are outside this valid-input contract.

For this exercise, assume coordinates are zero-based and both endpoints are inclusive. Return one row [top,left,bottom,right] per rectangle, ordered by its top-left row and then column. This four-integer row is the callable encoding of the source's two corner coordinates. An input with no zeros returns an empty matrix.

Function

allRectangleBounds(matrix: int[][]) → int[][]

Examples

Example 1

matrix = [[0,1,1,1,1],[1,1,0,0,1],[0,1,0,0,1],[0,1,1,1,1],[1,0,1,1,1]]return = [[0,0,0,0],[1,2,2,3],[2,0,3,0],[4,1,4,1]]

The source matrix is retained. Indeed reports four rectangles but does not give their coordinates; these bounds are independently derived under the stated component assumption.

Example 2

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

This authored example contains two diagonally touching filled rectangles.

Example 3

matrix = [[1,1],[1,1]]return = []

This authored example contains no zero rectangle.

Constraints

  • For this exercise, assume row and column counts are each from 1 through 30, and all rows have the same length.
  • Every cell is the integer 0 or 1.
  • Each orthogonally connected zero component fills its bounding rectangle.

More Indeed problems

See Indeed hiring insights
public int[][] allRectangleBounds(int[][] matrix) {
    // Write your code here.
    return new int[0][];
}
matrix[[0,1,1,1,1],[1,1,0,0,1],[0,1,0,0,1],[0,1,1,1,1],[1,0,1,1,1]]
expected[[0,0,0,0],[1,2,2,3],[2,0,3,0],[4,1,4,1]]
Checking account…