LeetCode 598: Range Addition II

Problem Restatement

We are given an m x n matrix initialized with all zeroes.

We are also given a list of operations ops.

Each operation has the form:

[a, b]

This means we increment every cell (x, y) where:

0 <= x < a
0 <= y < b

In other words, each operation increments a rectangle starting from the top-left corner.

After performing all operations, return the number of cells containing the maximum value. If there are no operations, every cell remains 0, so every cell is maximum. The official statement uses ops[i] = [a_i, b_i] and asks for the number of maximum integers after all operations.

Input and Output

Example function shape:

def maxCount(m: int, n: int, ops: list[list[int]]) -> int:
    ...

Examples

Example 1:

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

Output:

4

After [2, 2], the top-left 2 x 2 area is incremented.

After [3, 3], the whole 3 x 3 matrix is incremented.

The top-left 2 x 2 area is incremented twice, so those four cells contain the maximum value.

Example 2:

m = 3
n = 3
ops = []

Output:

9

There are no operations, so all 3 * 3 = 9 cells have value 0, which is the maximum.

First Thought: Simulate the Matrix

A direct solution is to create the matrix and apply every operation.

For each operation [a, b], we loop through rows 0 to a - 1 and columns 0 to b - 1, incrementing each cell.

This works for small inputs, but it is too slow and memory-heavy.

The constraints allow m and n to be as large as 4 * 10^4, so the matrix could have far too many cells to store explicitly. The number of operations can also be up to 10^4.

Key Insight

Every operation starts from the same top-left cell (0, 0).

So the cells with the maximum value are exactly the cells that are included in every operation.

For example:

ops = [[2, 2], [3, 3]]

The first operation covers rows:

0, 1

and columns:

0, 1

The second operation covers rows:

0, 1, 2

and columns:

0, 1, 2

The overlap of all operations is the top-left 2 x 2 rectangle.

In general, the common overlap has:

min_a rows
min_b columns

where min_a is the minimum first value among all operations, and min_b is the minimum second value among all operations.

So the answer is:

min_a * min_b

If ops is empty, no cell is incremented, so every cell has the same maximum value. The answer is:

m * n

Algorithm

1. Initialize min_row = m.
2. Initialize min_col = n.
3. For each operation [a, b]:
   • Set min_row = min(min_row, a).
   • Set min_col = min(min_col, b).
4. Return min_row * min_col.

This also handles empty ops, because min_row and min_col remain m and n.

Correctness

Each operation increments a top-left rectangle. A cell receives the maximum possible value exactly when it is incremented by every operation.

A cell (x, y) is included in an operation [a, b] exactly when x < a and y < b.

Therefore, a cell is included in all operations exactly when:

x < min_a
y < min_b

where min_a is the minimum a over all operations, and min_b is the minimum b over all operations.

There are exactly min_a * min_b such cells.

All other cells are excluded from at least one operation, so they are incremented fewer times and cannot contain the maximum value.

If there are no operations, every cell remains 0, so all m * n cells contain the maximum value. Since the algorithm initializes min_row = m and min_col = n, it returns m * n in this case.

Therefore, the algorithm returns the correct count.

Complexity

Let:

k = len(ops)

Implementation

class Solution:
    def maxCount(self, m: int, n: int, ops: list[list[int]]) -> int:
        min_row = m
        min_col = n

        for a, b in ops:
            min_row = min(min_row, a)
            min_col = min(min_col, b)

        return min_row * min_col

Code Explanation

We start with the whole matrix as the possible maximum region:

min_row = m
min_col = n

Each operation can only shrink the region that is incremented by every operation.

For each operation:

for a, b in ops:

we update the common row bound:

min_row = min(min_row, a)

and the common column bound:

min_col = min(min_col, b)

Finally:

return min_row * min_col

returns the area of the rectangle included in every operation.

Testing

def run_tests():
    s = Solution()

    assert s.maxCount(3, 3, [[2, 2], [3, 3]]) == 4
    assert s.maxCount(3, 3, []) == 9
    assert s.maxCount(3, 3, [[3, 3]]) == 9
    assert s.maxCount(5, 4, [[3, 4], [2, 2], [5, 3]]) == 4
    assert s.maxCount(1, 1, []) == 1
    assert s.maxCount(10, 10, [[1, 10], [10, 1]]) == 1

    print("all tests passed")

run_tests()

Test meaning: