Painting Rows and Columns

Medium

There is a size × size grid, initially all zeros. You get a list of paint operations paints, each a triple [kind, index, value]: - if kind == 0, every cell of row index is set to value; - if kind == 1, every cell of column index is set to value. Operations are applied in order, later ones overwrite earlier ones. Return the sum of all numbers in the grid after the last operation. The grid can be huge, so do not build it.

Example 1

size=2, paints=[[0, 0, 5], [1, 1, 2]] → 9

First the top row becomes [5, 5], then the right column is repainted to 2: the grid is [[5, 2], [0, 2]], sum 9.

Example 2

size=3, paints=[[1, 0, 4], [1, 0, 1], [0, 2, 3]] → 11

The left column is painted 4, then 1. Then the bottom row gets 3, including its left cell. Sum: 1 + 1 + 3 + 3 + 3 = 11.

Constraints

1 ≤ size ≤ 10⁴
1 ≤ len(paints) ≤ 5·10⁴
kind is 0 or 1
0 ≤ index < size
0 ≤ value ≤ 10⁵

Have you seen this problem in a real interview?

Solved by0

Tried by0

Submissions0

Acceptance—

Topics

Array Hash Table

Similar problems

Sudoku Board Without Clashes Medium Anagram Buckets Medium Zero Out the Crosses Medium Tree From Pre-Order and In-Order Walks Medium Tree From In-Order and Post-Order Walks Medium

Input

size=2, paints=[[0, 0, 5], [1, 1, 2]]

Expected

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