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
My Solution
Since we always increment value starting from 0 in both the rows and columns, we know that the elements with the maximum value will reside in the smallest range in rows multiplied by the smallest range in columns. We iterate through ops to find the minimum y and the minimum x. We return the min_y * min_x.
Time complexity is O(n), where n is the number of entries in ops. Space complexity is O(1) since we only require constant extra space.
class Solution {
public int maxCount(int m, int n, int[][] ops) {
int min_y = m;
int min_x = n;
for (int i = 0; i < ops.length; i++) {
int[] op = ops[i];
min_y = Math.min(min_y, op[0]);
min_x = Math.min(min_x, op[1]);
}
return (min_y * min_x);
}
}