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 * 1040 <= ops.length <= 104ops[i].length == 21 <= ai <= m1 <= bi <= nProblem Overview: You start with an m x n matrix filled with zeros. Each operation [a, b] increments every cell in the submatrix from (0,0) to (a-1,b-1). After applying all operations, the task is to count how many cells contain the maximum value in the matrix.
Approach 1: Minimize Rows and Columns (O(k) time, O(1) space)
The key observation is that every operation increments a rectangle starting from the top-left corner. The cells that end up with the largest value are the ones included in all operations. That overlapping region is determined by the smallest row boundary and the smallest column boundary across all operations. Iterate through the operations, track minRow = min(minRow, a) and minCol = min(minCol, b). The number of cells with the maximum value becomes minRow * minCol. This works because each operation overlaps in the top-left region, and the tightest bounds define the common intersection. Time complexity is O(k) where k is the number of operations, and space complexity is O(1). This approach mainly relies on simple iteration over an array of operations and basic math reasoning.
Approach 2: Direct Simulation (Less Efficient) (O(k * m * n) time, O(m * n) space)
A straightforward method is to simulate the process exactly as described. Create an m x n matrix initialized with zeros. For each operation [a, b], iterate through rows 0..a-1 and columns 0..b-1 and increment each cell. After processing all operations, scan the matrix to find the maximum value and count how many cells contain it. While easy to implement, this approach performs unnecessary repeated work since many cells are incremented multiple times across operations. The time complexity grows to O(k * m * n) with O(m * n) space, which becomes inefficient for larger matrices.
Recommended for interviews: The minimize rows and columns approach is the expected solution. It shows you recognize the overlapping rectangle pattern rather than simulating updates. Starting with the direct simulation demonstrates understanding of the problem mechanics, but identifying the intersection of all operations and reducing the solution to minRow * minCol demonstrates strong problem-solving skills and comfort with array traversal and simple mathematical reasoning.
To solve this problem efficiently, observe that each operation affects a submatrix starting from the top-left corner. Thus, the final result of the operations is determined by the smallest intersected submatrix affected by all operations. Find the minimum value of "a" and "b" from all operations in ops. This will give you the dimensions of the area where the maximum integers will exist after applying all operations.
The key insight is that the size of the submatrix affected by all operations determines the count of maximum numbers in the final matrix.
This solution iterates over all operations provided and finds the minimum values of rows and columns from the operations. These minimums define the dimensions of the submatrix that will have the maximum value after all operations. We simply calculate the area of this submatrix to get the count of maximum integers.
Time Complexity: O(k), where k is the number of operations.
Space Complexity: O(1), as we are using only a few extra variables.
This approach simulates the operations directly on the matrix. For each operation, we iterate through the specified submatrix and increment the values. Finally, we determine the number of times the maximum value occurs in the matrix. Although this method is less efficient due to its higher computational cost, it reinforces understanding of the problem.
This solution creates a matrix of size m x n and sets all values to zero. For each operation, it increments the values within the specified submatrix. After processing all operations, it finds the maximum value in the matrix and counts its occurrences.
Time Complexity: O(m * n * k), where m and n are the dimensions of the matrix, and k is the number of operations.
Space Complexity: O(m * n), for the matrix.
We notice that the intersection of all operation submatrices is the submatrix where the final maximum integer is located, and each operation submatrix starts from the top-left corner (0, 0). Therefore, we traverse all operation submatrices to find the minimum number of rows and columns. Finally, we return the product of these two values.
Note that if the operation array is empty, the number of maximum integers in the matrix is m times n.
The time complexity is O(k), where k is the length of the operation array ops. The space complexity is O(1).
Python
Java
C++
Go
TypeScript
Rust
JavaScript
| Approach | Complexity |
|---|---|
| Approach 1: Minimize Rows and Columns | Time Complexity: O(k), where k is the number of operations. Space Complexity: O(1), as we are using only a few extra variables. |
| Approach 2: Direct Simulation (Less Efficient) | Time Complexity: O(m * n * k), where m and n are the dimensions of the matrix, and k is the number of operations. Space Complexity: O(m * n), for the matrix. |
| Brain Teaser | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Minimize Rows and Columns | O(k) | O(1) | Best approach for interviews and production. Uses the intersection of all operations. |
| Direct Simulation | O(k * m * n) | O(m * n) | Useful for understanding the problem or when constraints are extremely small. |
Range Addition II Leetcode 598 | Live coding session 🔥🔥🔥 • Coding Decoded • 2,994 views views
Watch 9 more video solutions →Practice Range Addition II with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor