589 Range Addition II

1. Description

You are given an \(m \times n\) matrix M initialized with all 0's and an array of operations ops, where \(ops[i] = [a_i, b_i]\) means M[x][y] should be incremented by one for all \(0 <= x < = a_i\) and \(0 <= y =<= b_i\). Count and return the number of maximum integers in the matrix after performing all the operations.

 

constraints :

• 1 <= m, n <= 4 * \(10^{4}\)
• 0 <= ops.length <= \(10^{4}\)
• ops[i].length == 2
• 1 <= a_i <= m
• 1 <= b_i <= n

 

2. Algorithms

Maximum integers in the matrix after performing all the operations have minimum boundaries between all the input ops. For example, if we got [[2, 1], [3, 3], [3, 2], [3, 3], [2, 2], [3, 3]] as input, then our minimum boundaries which have the number of maximum integers becomes [2, 2] and result will be 4 (2 times 2).

 

1. Start
2. If the length of ops is 0, return m * n.
3. Calculate minimum boundaries of all rows and all cols and multiply them. 
4. Return the result.
5. End

 

3. Codes

class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
        if len(ops) == 0 : return m * n 
        
        row_min = min(ops, key = lambda x : x[0])[0]
        row_col = min(ops, key = lambda x : x[1])[1] 
        return row_min * row_col
        
# Faster Codes
class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
		min_row = m
        min_col = n 
        
        for op in ops : 
        	min_row = min(op[0], min_row) 
            min_col = min(op[1], min_col) 
        
        return min_row * min_col

4. Conclusion