Range Addition II

EasyMatrixmath

Solve this the way you would in the interview: out loud, on a timer, with an AI interviewer asking follow-ups while you code. You get a scored report at the end.

Practice this as a mock interviewFree to start, no account needed

Problem

Start with an m x n matrix M filled with zeros. You are given a list of operations ops, where ops[i] = [a, b] means: add 1 to every cell M[x][y] with 0 <= x < a and 0 <= y < b. After applying every operation, return how many cells hold the maximum value in the matrix. If ops is empty, every cell is 0 and all m * n cells tie for the maximum. The matrix can be huge, so avoid building it: aim for O(k) time where k is the number of operations.

Examples

Input: m = 3, n = 3, ops = [[2,2],[3,3]]
Output: 4
The top-left 2x2 block is incremented twice and holds the maximum value 2.
Input: m = 3, n = 3, ops = []
Output: 9
No operations, so all 9 cells tie at 0.

Constraints

  • 1 <= m, n <= 4 * 10^4
  • 0 <= ops.length <= 10^4
  • ops[i].length == 2
  • 1 <= a <= m
  • 1 <= b <= n

What the interviewer grades

A correct solution is one of five scores. The report also grades problem understanding (did you clarify inputs and edge cases before coding), problem solving, communication while you work, code quality, and testing. See a sample report, or read up on the pattern in the lessons.

More math problems