Scale Engineer

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] = [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:

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

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.

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;    }}

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

Solutions

/** * @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;  };

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 →

Next problem