# Range Addition II
**Difficulty:** EASY
[External](https://leetcode.com/problems/range-addition-ii)
Canonical: https://scaleengineer.com/dsa/problems/range-addition-ii
**Patterns:** [Math](https://scaleengineer.com/dsa/patterns/math)
**Data structures:** Array
**Companies:** [IXL](https://scaleengineer.com/companies/ixl)
---
## Problem
You are given an `m x n` matrix `M` initialized with all `0`'s and an array of operations `ops`, where `ops[i] = [ai, bi]` means `M[x][y]` should be incremented by one for all `0 <= x < ai` and `0 <= y < bi`.

Count and return _the number of maximum integers in the matrix after performing all the operations_.

**Example 1:**

![](https://assets.glich.co/dsa/range-addition-ii/image0.jpg) 

**Input:** m = 3, n = 3, ops = [[2,2],[3,3]]
**Output:** 4
**Explanation:** The maximum integer in M is 2, and there are four of it in M. So return 4.

**Example 2:**

**Input:** m = 3, n = 3, ops = [[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3]]
**Output:** 4

**Example 3:**

**Input:** m = 3, n = 3, ops = []
**Output:** 9

**Constraints:**

* `1 <= m, n <= 4 * 104`
* `0 <= ops.length <= 104`
* `ops[i].length == 2`
* `1 <= ai <= m`
* `1 <= bi <= n`

# Approaches
## Brute-Force Simulation
This approach directly simulates the process described in the problem. We create an actual `m x n` matrix and perform each increment operation on it. After all operations are completed, we traverse the matrix to find the maximum value and count its occurrences.
**Time:** O(k * m * n), where `k` is the number of operations. For each of the `k` operations, we might update up to `m * n` cells. Finding the max and count takes another `O(m * n)`. This is highly inefficient and will time out for large inputs. · **Space:** O(m * n) to store the matrix. This can lead to a Memory Limit Exceeded error for large `m` and `n`.
**Pros:** Simple to understand and implement as it directly follows the problem statement.
**Cons:** Extremely inefficient in terms of both time and space.; Will not pass the tests with larger constraints due to Time Limit Exceeded (TLE) and Memory Limit Exceeded (MLE).
### Explanation
We start by initializing an `m x n` integer matrix with all values set to 0. We then loop through every operation `[a, b]` in the `ops` array. For each operation, we use a nested loop to iterate through the sub-matrix from row `0` to `a-1` and column `0` to `b-1`. In this sub-matrix, we increment the value of each cell `M[i][j]` by one. After processing all operations, the matrix `M` holds the final values. We then iterate through the entire matrix one more time to find the maximum value present. Finally, we perform another pass through the matrix to count how many cells are equal to this maximum value. This count is our result.

```java
class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        if (ops == null || ops.length == 0) {
            return m * n;
        }

        int[][] matrix = new int[m][n];

        for (int[] op : ops) {
            int row_lim = op[0];
            int col_lim = op[1];
            for (int i = 0; i < row_lim; i++) {
                for (int j = 0; j < col_lim; j++) {
                    matrix[i][j]++;
                }
            }
        }

        int maxVal = 0;
        if (m > 0 && n > 0) {
            // The top-left element is guaranteed to be one of the maximums
            maxVal = matrix[0][0];
        }

        int count = 0;
        for (int i = 0; i < m; i++) {
            for (int j = _0; j < n; j++) {
                if (matrix[i][j] == maxVal) {
                    count++;
                }
            }
        }
        return count;
    }
}
```
### Algorithm
- Create a 2D array `matrix` of size `m x n` and initialize all its elements to 0.
- For each operation `op` in `ops`:
    - Let `row_lim = op[0]` and `col_lim = op[1]`.
    - For `i` from `0` to `row_lim - 1`:
        - For `j` from `0` to `col_lim - 1`:
            - `matrix[i][j]++`.
- Initialize `max_val = 0`.
- Iterate through `matrix` to find the maximum value and store it in `max_val`.
- Initialize `count = 0`.
- Iterate through `matrix` again. If `matrix[i][j] == max_val`, increment `count`.
- Return `count`.

## Single Pass to Find Minimum Boundaries
A more insightful approach recognizes that the maximum value in the matrix will be achieved only in the cells that are affected by *every single* operation. The region affected by all operations is the intersection of the regions of each individual operation. This intersection is a rectangle whose dimensions are determined by the minimum row and column limits from all operations.
**Time:** O(k), where `k` is the number of operations (`ops.length`). We iterate through the `ops` array only once. · **Space:** O(1). We only use a few variables to store the minimum row and column values, regardless of the input size.
**Pros:** Extremely efficient in both time and space.; Simple and elegant solution based on a key observation.
**Cons:** Requires a logical leap to understand why this works, instead of direct simulation.
### Explanation
Each operation `[a_i, b_i]` increments a rectangle of cells from `(0, 0)` to `(a_i-1, b_i-1)`. A cell `(x, y)` is incremented by an operation `[a_i, b_i]` if `x < a_i` and `y < b_i`. For a cell to be incremented by *all* operations, it must satisfy `x < a_i` and `y < b_i` for all `i`. This is equivalent to `x < min(all a_i)` and `y < min(all b_i)`. Therefore, the cells with the maximum value (which will be `ops.length`) form a rectangle of size `min_a x min_b`, where `min_a` is the minimum of all `a_i`'s and `min_b` is the minimum of all `b_i`'s. The number of such cells is simply `min_a * min_b`. We can find these minimums in a single pass through the `ops` array. If `ops` is empty, no operations are performed. All cells remain 0, which is the maximum value. The number of such cells is `m * n`. Our logic handles this if we initialize our minimums to `m` and `n`.

```java
class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        int min_a = m;
        int min_b = n;

        for (int[] op : ops) {
            min_a = Math.min(min_a, op[0]);
            min_b = Math.min(min_b, op[1]);
        }

        return min_a * min_b;
    }
}
```
### Algorithm
- Initialize `min_row = m` and `min_col = n`.
- Iterate through each operation `op` in `ops`.
    - Update `min_row = min(min_row, op[0])`.
    - Update `min_col = min(min_col, op[1])`.
- Return `min_row * min_col`.

# Solutions
### JavaScript

```javascript
/** * @param {number} m * @param {number} n * @param {number[][]} ops * @return {number} */ var maxCount =
  function (m, n, ops) {
    for (const [a, b] of ops) {
      m = Math.min(m, a);
      n = Math.min(n, b);
    }
    return m * n;
  };

```

### Java

```java
class Solution {
public
  int maxCount(int m, int n, int[][] ops) {
    for (int[] op : ops) {
      m = Math.min(m, op[0]);
      n = Math.min(n, op[1]);
    }
    return m * n;
  }
}

```

### CPP

```cpp
class Solution {
public:
  int maxCount(int m, int n, vector<vector<int>> &ops) {
    for (auto op : ops) {
      m = min(m, op[0]);
      n = min(n, op[1]);
    }
    return m * n;
  }
};

```

### Python

```python
class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int: for a, b in ops: m = min(m, a) n = min(n, b) return m * n  # from functools import reduce class Solution ( object ): def maxCount ( self , m , n , ops ): """ :type m: int :type n: int :type ops: List[List[int]] :rtype: int """ return reduce ( operator . mul , map ( min , zip ( * ops + [[ m , n ]])))

```