Range Addition II — LeetCode 598 Python Solution

The 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.

Example

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.

Python solution

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

Complexity

Pattern: Math and Number Theory

Find the closed form, the invariant, or the modular identity — and skip the loop entirely. LeetCode 598. Range Addition II is filed here on both counts: the reference solution below belongs to the algorithm family this hub collects, and LeetCode tags it Math.

The math and number theory guide has the Python template for the pattern and the 485 LeetCode problems that use it.

Related problems