LeetCode 598 - Range Addition II

Difficulty: 🟢 Easy
Topics: Array, Math

Solution

Problem Understanding

The problem presents an m x n matrix M initialized with all zeros. You are also given an array of operations ops, where each operation ops[i] = [ai, bi] instructs you to increment by one all elements in the submatrix defined by the top-left corner (0,0) and the bottom-right corner (ai-1, bi-1). After applying all operations, the goal is to determine how many elements in the matrix contain the maximum value.

In simpler terms, each operation defines a rectangle in the matrix, and every element inside that rectangle gets incremented by one. After performing all the operations, some elements may have higher values than others, and we are asked to count how many elements reach the highest possible value.

The input constraints are important. The matrix dimensions m and n can be up to 40,000, and the number of operations can be up to 10,000. These constraints imply that a naive approach that explicitly updates every element of the matrix per operation would be too slow and memory-intensive. Instead, an efficient algorithm is required.

Key edge cases include scenarios where there are no operations, where operations fully overlap, and where operations partially overlap. The problem guarantees that each operation will be within the matrix boundaries.

Approaches

The brute-force approach is straightforward: initialize the matrix, iterate through each operation, and increment all affected elements. After all operations, scan the matrix to find the maximum value and count its occurrences. While this approach is correct, it is infeasible for the given constraints because it could require updating up to m * n elements per operation, leading to potentially hundreds of millions or billions of updates.

The optimal approach comes from a key observation: the maximum value in the matrix occurs at the intersection of all the rectangles defined by the operations. If you imagine each operation as defining a rectangle from (0,0) to (ai-1, bi-1), the region where all these rectangles overlap will be incremented in every operation. Therefore, the size of this intersection rectangle is min(ai) x min(bi) across all operations. If there are no operations, the entire matrix has the maximum value, which is 0, and all m*n elements are counted.

This insight eliminates the need to simulate the matrix entirely. We only need to track the minimum ai and bi values across all operations to compute the area of the overlapping region.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(len(ops) * m * n)	O(m * n)	Updates the entire matrix per operation; infeasible for large inputs
Optimal	O(len(ops))	O(1)	Only tracks minimum boundaries of operations; computes result directly

Algorithm Walkthrough

Check for empty operations: If ops is empty, no increments occur, so every element remains at 0. Return m * n because the entire matrix is at the maximum value.
Initialize variables: Set min_row to m and min_col to n. These will track the intersection rectangle.
Iterate through operations: For each operation [ai, bi], update min_row to the smaller of min_row and ai, and min_col to the smaller of min_col and bi. This ensures that at the end, min_row and min_col represent the bounds of the overlap.
Compute result: Multiply min_row and min_col to obtain the number of elements in the intersection rectangle, which is exactly the number of maximum integers in the matrix.
Return result: Output min_row * min_col.

Why it works: The algorithm relies on the invariant that the maximum value only occurs in the region that every operation affects. By tracking the minimum ai and bi, we are effectively finding the intersection of all operation rectangles. Every cell outside this intersection receives fewer increments than cells inside, guaranteeing that the intersection contains all maximum elements.

Python Solution

from typing import List

class Solution:
    def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
        if not ops:
            return m * n
        
        min_row, min_col = m, n
        
        for ai, bi in ops:
            min_row = min(min_row, ai)
            min_col = min(min_col, bi)
        
        return min_row * min_col

The code first checks if there are no operations and returns the full matrix size. It then iterates through each operation to find the smallest ai and bi. Multiplying these gives the number of maximum elements. This matches the algorithm walkthrough directly and avoids unnecessary matrix updates.

Go Solution

func maxCount(m int, n int, ops [][]int) int {
    if len(ops) == 0 {
        return m * n
    }

    minRow, minCol := m, n

    for _, op := range ops {
        if op[0] < minRow {
            minRow = op[0]
        }
        if op[1] < minCol {
            minCol = op[1]
        }
    }

    return minRow * minCol
}

The Go implementation mirrors the Python version. It checks for an empty ops slice, initializes minRow and minCol, and iterates through the slice updating these values. Multiplication of the minimum row and column sizes gives the result. Edge cases such as empty operations or full overlap are handled directly by the min tracking.

Worked Examples

Example 1:

Input: m = 3, n = 3, ops = [[2,2],[3,3]]

Initialize min_row = 3, min_col = 3
First operation [2,2]: min_row = min(3,2) = 2, min_col = min(3,2) = 2
Second operation [3,3]: min_row = min(2,3) = 2, min_col = min(2,3) = 2
Maximum element count = 2 * 2 = 4

Example 2:

Input: m = 3, n = 3, ops = []

No operations → maximum value occurs across all cells
Maximum element count = 3 * 3 = 9

Complexity Analysis

Measure	Complexity	Explanation
Time	O(len(ops))	Iterates through the operations once to track minimum boundaries
Space	O(1)	Only two integers are used to track the minimum row and column

The optimal solution is extremely efficient because it reduces the problem to a simple min-tracking operation without constructing or modifying a large matrix.

Test Cases

# Provided examples
assert Solution().maxCount(3, 3, [[2,2],[3,3]]) == 4  # basic overlap
assert Solution().maxCount(3, 3, []) == 9           # no operations
assert Solution().maxCount(3, 3, [[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3],[2,2],[3,3],[3,3],[3,3]]) == 4  # repeated ops

# Edge cases
assert Solution().maxCount(1, 1, []) == 1           # single cell, no ops
assert Solution().maxCount(1, 1, [[1,1]]) == 1     # single cell, single op
assert Solution().maxCount(5, 5, [[5,3],[3,5]]) == 3*3  # partial overlap
assert Solution().maxCount(5, 5, [[1,1],[2,2]]) == 1  # smallest intersection
assert Solution().maxCount(10000, 10000, [[5000,5000]]) == 5000*5000  # large numbers

Test	Why
[[2,2],[3,3]]	basic overlapping operations
[]	no operations, entire matrix is maximum
multiple repeated ops	ensures repeated operations don't affect counting
single cell, no ops	smallest possible matrix
single cell, single op	ensures single increment is handled
partial overlap	operations partially intersect
smallest intersection	tests minimal intersection area
large numbers	stress test for large `m` and `n`

Edge Cases

No operations: When ops is empty, all cells retain the initial value 0. A naive implementation that attempts to access ops[0] would fail, but our solution handles this by checking for empty ops and returning m * n.
Single cell matrix: A matrix of size 1x1 is trivial but can expose off-by-one errors in min calculations. The algorithm correctly handles this by using min_row = m and min_col = n as initial values and updating them appropriately.
Operations larger than matrix dimensions: Although constraints guarantee 1 <= ai <= m and 1 <= bi <= n, some inputs may push to the upper bound of 40,000. The algorithm remains efficient because it does not construct the full matrix; it only tracks minimum values, avoiding memory or