FastPrepInclusive Rectangle Coverage Counts
Problem · Matrix

Inclusive Rectangle Coverage Counts

Learn this problem
● MediumGoogle logoGoogleFULLTIMEONSITE INTERVIEW
See Google hiring insights

Problem statement

You are given an integer n and an array rectangles. Start with an n x n matrix of zeros.

Each rectangle is represented as [top, left, bottom, right] using zero-based row and column indices. Its boundaries are inclusive. For every rectangle, add 1 to every matrix cell whose row is between top and bottom and whose column is between left and right.

Return the completed matrix of coverage counts.

Function

countRectangleCoverage(n: int, rectangles: int[][]) → int[][]

Examples

Example 1

n = 3rectangles = [[0,0,1,1],[1,1,2,2]]return = [[1,1,0],[1,2,1],[0,1,1]]

The two rectangles overlap only at (1,1), so that cell has count 2. Cells covered by one rectangle have count 1.

Example 2

n = 4rectangles = [[0,1,3,2],[1,0,2,3],[2,2,2,2]]return = [[0,1,1,0],[1,2,2,1],[1,2,3,1],[0,1,1,0]]

The vertical and horizontal rectangles overlap across rows 1 and 2, columns 1 and 2. The one-cell rectangle raises (2,2) to 3.

Example 3

n = 2rectangles = []return = [[0,0],[0,0]]

With no rectangles, every cell keeps its initial coverage count of 0.

Constraints

  • 1 <= n <= 500
  • 0 <= rectangles.length <= 100000
  • rectangles[i].length == 4
  • For every rectangle, 0 <= top <= bottom < n and 0 <= left <= right < n.
  • Rectangle boundaries are inclusive.

More Google problems

drafts saved locally
public int[][] countRectangleCoverage(int n, int[][] rectangles) {
    // Write your code here.
}
n3
rectangles[[0,0,1,1],[1,1,2,2]]
expected[[1,1,0],[1,2,1],[0,1,1]]
checking account