Skip to content

598. Range Addition II

Description

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

Solutions

Solution 1: Brain Teaser

Thinking

Each update adds one to a top-left submatrix. The final maximum equals the number of updates, and it occupies the intersection of those submatrices. Every update starts at \((0,0)\), so the intersection is \(\min a_i\) by \(\min b_i\).

One pass over the operations; the product is the answer. No \(m \times n\) difference array is required.

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 \(\textit{ops}\). The space complexity is \(O(1)\).

1
2
3
4
5
6
class Solution:
    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

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

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

1
2
3
4
5
6
7
func maxCount(m int, n int, ops [][]int) int {
    for _, op := range ops {
        m = min(m, op[0])
        n = min(n, op[1])
    }
    return m * n
}

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

1
2
3
4
5
6
7
8
9
impl Solution {
    pub fn max_count(mut m: i32, mut n: i32, ops: Vec<Vec<i32>>) -> i32 {
        for op in ops {
            m = m.min(op[0]);
            n = n.min(op[1]);
        }
        m * n
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
/**
 * @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;
};

Comments