Range Addition II

easy math

Problem

Start with an m×n zero matrix. Each op [a, b] increments cells in [0..a)×[0..b). Return count of cells equal to the max.

Inputm=3 n=3 ops=[[2,2],[3,3]]

Output4

Min a=2, min b=2; intersection cells = 2·2 = 4.

input

def max_count(m, n, ops):
    if not ops: return m * n
    a = min(o[0] for o in ops); b = min(o[1] for o in ops)
    return a * b

function maxCount(m, n, ops) {
  if (!ops.length) return m * n;
  const a = Math.min(...ops.map(o => o[0])), b = Math.min(...ops.map(o => o[1]));
  return a * b;
}

int maxCount(int m, int n, int[][] ops) {
    if (ops.length == 0) return m * n;
    int a = Integer.MAX_VALUE, b = Integer.MAX_VALUE;
    for (int[] o : ops) { a = Math.min(a, o[0]); b = Math.min(b, o[1]); }
    return a * b;
}

int maxCount(int m, int n, vector>& ops) {
    if (ops.empty()) return m * n;
    int a = INT_MAX, b = INT_MAX;
    for (auto& o : ops) { a = min(a, o[0]); b = min(b, o[1]); }
    return a * b;
}

Explanation

Every operation [a, b] adds 1 to the same corner block: the top-left rectangle from row 0 to a and column 0 to b. So we never need to build or scan the whole matrix — we can reason about it directly.

A cell ends up with the maximum value only if it was touched by every single operation. A cell is inside operation [a, b] when its row is below a and its column is below b. To be inside all of them, the cell must fit within the smallest rectangle of all.

That smallest rectangle is min(a) rows tall and min(b) columns wide. The number of cells in it — and therefore the count of maximum cells — is simply min(a) × min(b).

One edge case: if there are no operations, nothing was incremented, so all m × n cells share the max value of 0.

Example: m=3, n=3, ops=[[2,2],[3,3]]. The smallest a is 2 and smallest b is 2, so the answer is 2 × 2 = 4.

Time: O(k) Space: O(1)