Range Addition II

Difficulty: Easy | Acceptance: 58.70% | Paid: No Topics: Array, Math

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 increment all elements M[x][y] for 0 <= x < ai and 0 <= y < bi.

Count and return the number of maximum integers in the matrix after performing all the operations.

• Examples
• Constraints
• Brute Force Simulation
• Mathematical Intersection

Examples

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 * 10⁴
0 <= ops.length <= 10⁴
ops[i].length == 2
1 <= ai <= m
1 <= bi <= n

Brute Force Simulation

Intuition Simulate the process exactly as described by creating the matrix and applying each operation to the relevant submatrix.

Steps

• Initialize an m x n matrix with all zeros.
• Iterate through each operation in the ops array.
• For each operation [a, b], iterate through rows 0 to a-1 and columns 0 to b-1, incrementing each cell by 1.
• After all operations, find the maximum value in the matrix.
• Count how many times this maximum value appears and return the count.

class Solution:
    def maxCount(self, m: int, n: int, ops: list[list[int]]) -> int:
        M = [[0] * n for _ in range(m)]
        for a, b in ops:
            for i in range(a):
                for j in range(b):
                    M[i][j] += 1
        max_val = 0
        count = 0
        for i in range(m):
            for j in range(n):
                if M[i][j] > max_val:
                    max_val = M[i][j]
                    count = 1
                elif M[i][j] == max_val:
                    count += 1
        return count

Complexity

• Time: O(K * M * N) where K is the number of operations. In the worst case, this is very slow.
• Space: O(M * N) to store the matrix.
• Notes: This approach is not efficient for large inputs but demonstrates the literal interpretation of the problem.

Mathematical Intersection

Intuition Since every operation starts at the top-left corner (0, 0), the cells that are incremented the most times are the ones common to all operation rectangles. The maximum value is determined by the overlap of all operations.

Steps

• Initialize min_row to m and min_col to n.
• Iterate through each operation [a, b].
• Update min_row to be the minimum of current min_row and a.
• Update min_col to be the minimum of current min_col and b.
• The number of maximum integers is the area of the overlapping rectangle: min_row * min_col.

class Solution:
    def maxCount(self, m: int, n: int, ops: list[list[int]]) -> int:
        min_a = m
        min_b = n
        for a, b in ops:
            min_a = min(min_a, a)
            min_b = min(min_b, b)
        return min_a * min_b

Complexity

• Time: O(K) where K is the number of operations.
• Space: O(1) as we only store a few variables.
• Notes: This is the optimal solution, avoiding the need for matrix simulation.