# 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:

```python
[a, b]
```

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

```text
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

| Item | Meaning |
|---|---|
| `m` | Number of matrix rows |
| `n` | Number of matrix columns |
| `ops` | List of increment rectangles |
| Output | Number of cells with the maximum value |

Example function shape:

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

## Examples

Example 1:

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

Output:

```python
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:

```python
m = 3
n = 3
ops = []
```

Output:

```python
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:

```python
ops = [[2, 2], [3, 3]]
```

The first operation covers rows:

```text
0, 1
```

and columns:

```text
0, 1
```

The second operation covers rows:

```text
0, 1, 2
```

and columns:

```text
0, 1, 2
```

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

In general, the common overlap has:

```text
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:

```text
min_a * min_b
```

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

```text
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:

```text
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:

```text
k = len(ops)
```

| Metric | Value | Why |
|---|---:|---|
| Time | `O(k)` | We scan the operations once |
| Space | `O(1)` | We store only two bounds |

## Implementation

```python
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:

```python
min_row = m
min_col = n
```

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

For each operation:

```python
for a, b in ops:
```

we update the common row bound:

```python
min_row = min(min_row, a)
```

and the common column bound:

```python
min_col = min(min_col, b)
```

Finally:

```python
return min_row * min_col
```

returns the area of the rectangle included in every operation.

## Testing

```python
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:

| Test | Why |
|---|---|
| `[[2, 2], [3, 3]]` | Main sample |
| Empty operations | Every cell is maximum |
| One full operation | Every cell is incremented once |
| Multiple shrinking bounds | Uses minimum row and column |
| `1 x 1` matrix | Minimum matrix size |
| Thin overlap | Common region can be one cell |