Range Addition II

Easy

#0567Time: 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`.1 company

Patterns

Math

Data structures

Array

Companies

IXL

Prompt

You are given an m x n matrix M initialized with all 0's and an array of operations ops, where ops[i] = [a_i, b_i] means M[x][y] should be incremented by one for all 0 <= x < a_i and 0 <= y < b_i.

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

Example 1:

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 * 10⁴
0 <= ops.length <= 10⁴
ops[i].length == 2
1 <= a_i <= m
1 <= b_i <= n

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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.

1class Solution {2    public int maxCount(int m, int n, int[][] ops) {3        if (ops == null || ops.length == 0) {4            return m * n;5        }6 7        int[][] matrix = new int[m][n];8 9        for (int[] op : ops) {10            int row_lim = op[0];11            int col_lim = op[1];12            for (int i = 0; i < row_lim; i++) {13                for (int j = 0; j < col_lim; j++) {14                    matrix[i][j]++;15                }16            }17        }18 19        int maxVal = 0;20        if (m > 0 && n > 0) {21            // The top-left element is guaranteed to be one of the maximums22            maxVal = matrix[0][0];23        }24 25        int count = 0;26        for (int i = 0; i < m; i++) {27            for (int j = _0; j < n; j++) {28                if (matrix[i][j] == maxVal) {29                    count++;30                }31            }32        }33        return count;34    }35}

Complexity

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

Trade-offs

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).

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.

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.

Walkthrough

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.

1class Solution {2    public int maxCount(int m, int n, int[][] ops) {3        int min_a = m;4        int min_b = n;5 6        for (int[] op : ops) {7            min_a = Math.min(min_a, op[0]);8            min_b = Math.min(min_b, op[1]);9        }10 11        return min_a * min_b;12    }13}

Complexity

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.

Trade-offs

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.

Solutions

Solution

1/** * @param {number} m * @param {number} n * @param {number[][]} ops * @return {number} */ var maxCount =2  function (m, n, ops) {3    for (const [a, b] of ops) {4      m = Math.min(m, a);5      n = Math.min(n, b);6    }7    return m * n;8  };

1class Solution {2public3  int maxCount(int m, int n, int[][] ops) {4    for (int[] op : ops) {5      m = Math.min(m, op[0]);6      n = Math.min(n, op[1]);7    }8    return m * n;9  }10}

1class Solution {2public:3  int maxCount(int m, int n, vector<vector<int>> &ops) {4    for (auto op : ops) {5      m = min(m, op[0]);6      n = min(n, op[1]);7    }8    return m * n;9  }10};

1class Solution:2    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 ]])))

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem