Layers of Paint on a Canvas

Medium

The canvas is an n × n grid with 0 in every cell. Rows and columns are numbered from zero. You get a list rects where rects[i] = [r1, c1, r2, c2] is a rectangle with top-left corner (r1, c1) and bottom-right corner (r2, c2), inclusive. Each rectangle adds one layer of paint: every cell (r, c) with r1 ≤ r ≤ r2 and c1 ≤ c ≤ c2 goes up by 1. Return the grid after all rectangles have been applied.

Example 1

n=3, rects=[[0, 0, 1, 2], [1, 1, 2, 1]] → [[1, 1, 1], [1, 2, 1], [0, 1, 0]]

The first rectangle covers the top two rows, the second the middle column in rows 1 and 2. Cell (1, 1) is painted twice.

Example 2

n=2, rects=[[1, 0, 1, 0], [1, 0, 1, 0], [0, 1, 0, 1]] → [[0, 1], [2, 0]]

Cell (1, 0) is painted twice, cell (0, 1) once.

Example 3

n=1, rects=[[0, 0, 0, 0]] → [[1]]

Constraints

1 ≤ n ≤ 500
1 ≤ len(rects) ≤ 10⁴
0 ≤ r1 ≤ r2 < n
0 ≤ c1 ≤ c2 < n

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Matrix Prefix Sum

Similar problems

Largest Light Square Medium Neighbourhood Sums in a Grid Medium K-th Largest Corner XOR Medium Three Heaviest Diamonds Medium Balanced Square in a Grid Medium

Input

n=3, rects=[[0, 0, 1, 2], [1, 1, 2, 1]]

Expected

[[1, 1, 1], [1, 2, 1], [0, 1, 0]]

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