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.

Examples

Example 1:

$$ \begin{bmatrix} 0 & 0 & 0 \\ 0 & 0 & 0 \\ 0 & 0 & 0 \end{bmatrix} \implies \begin{bmatrix} \colorbox{blue} 1 & \colorbox{blue} 1 & 0 \\ \colorbox{blue} 1 & \colorbox{blue} 1 & 0 \\ 0 & 0 & 0 \end{bmatrix} \implies \begin{bmatrix} \colorbox{blue} 2 & \colorbox{blue} 2 & \colorbox{blue} 1 \\ \colorbox{blue} 2 & \colorbox{blue} 2 & \colorbox{blue} 1 \\ \colorbox{blue} 1 & \colorbox{blue} 1 & \colorbox{blue} 1 \end{bmatrix} $$

1
2
3

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:

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

1
2

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

Solution

Method 1 - Counting

Here is the approach:

  1. Each operation affects the submatrix from the top-left corner (0, 0) to (ai-1, bi-1).
  2. The matrix cell with the maximum value will be at the intersection of all the smallest ai and bi.
  3. Therefore, find the minimum ai and bi from all operations, which determines the dimensions of the submatrix with the maximum value.
  4. The number of maximum integers in the matrix is the area of this submatrix.

Code

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13

public class Solution {
    public int maxCount(int m, int n, int[][] ops) {
        int minA = m;
        int minB = n;

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

        return minA * minB;
    }
}
 1
 2
 3
 4
 5
 6
 7
 8
 9
10

class Solution: 
    def maxCount(self, m, n, ops):
        min_a = m
        min_b = n
        
        for op in ops:
            min_a = min(min_a, op[0])
            min_b = min(min_b, op[1])
        
        return min_a * min_b

Complexity

  • Time: O(p), where p is the number of operations in ops. This is because we iterate through the ops array to determine the minimum ai and bi.
  • Space: O(1), as we only use a constant amount of additional space.