598. Range Addition II
Problem Description
You start with an m x n
matrix filled with all zeros. You're given a list of operations ops
, where each operation ops[i] = [ai, bi]
tells you to add 1 to all cells in the rectangle from the top-left corner (0, 0)
to position (ai-1, bi-1)
inclusive.
In other words, for each operation [ai, bi]
, you increment every cell M[x][y]
by 1 where 0 <= x < ai
and 0 <= y < bi
.
After performing all the operations, some cells will have higher values than others. Your task is to find how many cells contain the maximum value in the final matrix.
For example, if you have a 3x3 matrix and perform operation [2, 2]
, you would add 1 to the top-left 2x2 submatrix. After multiple operations, certain cells that are included in all operations will have the highest values.
The key insight is that cells that get incremented by every single operation will have the maximum value. These cells form a rectangle starting from (0, 0)
with dimensions equal to the minimum ai
and minimum bi
across all operations. The solution finds these minimum dimensions and returns their product, which gives the count of cells with the maximum value.
If no operations are performed (empty ops
array), all cells remain at 0, so all m * n
cells have the maximum value.
Intuition
Let's think about what happens when we perform these operations. Each operation [ai, bi]
adds 1 to a rectangle starting from (0, 0)
to (ai-1, bi-1)
.
The key observation is that all operations start from the same top-left corner (0, 0)
. This means the operations create overlapping rectangles, all anchored at the origin.
Which cells will have the maximum value after all operations? The cells that are included in every single operation. These are the cells that get incremented the most times - once for each operation.
Since all operations start from (0, 0)
, the intersection of all these rectangles is also a rectangle starting from (0, 0)
. The dimensions of this intersection rectangle are determined by the smallest ai
and smallest bi
values across all operations.
Think of it this way: if we have operations [3, 3]
, [2, 4]
, and [4, 2]
:
- The first operation covers a 3×3 area
- The second operation covers a 2×4 area
- The third operation covers a 4×2 area
The overlap of all three is a 2×2 area (minimum of 3, 2, 4 for rows = 2; minimum of 3, 4, 2 for columns = 2). Only the cells in this 2×2 area get incremented by all three operations, so they'll have the maximum value of 3.
This is why the solution simply finds min(all ai values)
and min(all bi values)
, then multiplies them together to get the count of cells with maximum value. The product m * n
gives us the area of the intersection rectangle, which equals the number of cells with the maximum value.
Learn more about Math patterns.
Solution Approach
The implementation is remarkably simple once we understand the problem's nature. We need to find the intersection of all operation rectangles, which is determined by the minimum dimensions across all operations.
Here's the step-by-step approach:
-
Initialize with matrix dimensions: Start with
m
andn
as the initial row and column bounds. These represent the maximum possible intersection area if no operations are performed. -
Find minimum dimensions: Iterate through each operation
[a, b]
in theops
array:- Update
m = min(m, a)
to track the smallest row dimension - Update
n = min(n, b)
to track the smallest column dimension
- Update
-
Calculate the result: Return
m * n
, which gives the area of the intersection rectangle.
The algorithm works because:
- Each operation covers a rectangle from
(0, 0)
to(a-1, b-1)
- The intersection of all these rectangles is from
(0, 0)
to(min_a - 1, min_b - 1)
- The number of cells in this intersection is
min_a * min_b
Edge Case: When the ops
array is empty, no operations are performed, so all cells remain at value 0. The function correctly returns m * n
since the initial values aren't modified.
Time Complexity: O(k)
where k
is the length of the ops
array, as we iterate through it once.
Space Complexity: O(1)
as we only use two variables to track the minimum dimensions.
The beauty of this solution is that we don't actually need to create or modify the matrix - we can determine the answer just by analyzing the operation boundaries.
Ready to land your dream job?
Unlock your dream job with a 3-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's walk through a concrete example with a 3×3 matrix and operations [[2,2], [3,3], [3,2]]
.
Initial Setup:
- Matrix dimensions: m = 3, n = 3
- All cells start at 0
Operation 1: [2,2]
- Adds 1 to rectangle from (0,0) to (1,1)
- Affects a 2×2 area
- Matrix after operation:
[1, 1, 0] [1, 1, 0] [0, 0, 0]
Operation 2: [3,3]
- Adds 1 to rectangle from (0,0) to (2,2)
- Affects a 3×3 area (entire matrix)
- Matrix after operation:
[2, 2, 1] [2, 2, 1] [1, 1, 1]
Operation 3: [3,2]
- Adds 1 to rectangle from (0,0) to (2,1)
- Affects a 3×2 area
- Final matrix:
[3, 3, 1] [3, 3, 1] [2, 2, 1]
Finding the Maximum:
- Maximum value in the matrix = 3
- Cells with value 3 form a 2×2 rectangle at the top-left
Using Our Algorithm: Instead of building the matrix, we find:
- min(2, 3, 3) = 2 (minimum row dimension)
- min(2, 3, 2) = 2 (minimum column dimension)
- Result = 2 × 2 = 4 cells with maximum value
The cells at positions (0,0), (0,1), (1,0), and (1,1) are included in all three operations, so they have the maximum value of 3. Our algorithm correctly identifies that there are 4 such cells.
Solution Implementation
1class Solution:
2 def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
3 """
4 Find the count of maximum values in an m x n matrix after applying operations.
5
6 Each operation ops[i] = [ai, bi] increments all elements in the submatrix
7 from (0,0) to (ai-1, bi-1) by 1.
8
9 Args:
10 m: Number of rows in the matrix
11 n: Number of columns in the matrix
12 ops: List of operations, where each operation is [row_limit, col_limit]
13
14 Returns:
15 Count of cells with the maximum value after all operations
16 """
17 # The maximum value will always be in the intersection of all operation ranges
18 # This intersection is defined by the minimum row and column limits
19 min_row_limit = m
20 min_col_limit = n
21
22 # Find the smallest operation range that covers all operations
23 for row_limit, col_limit in ops:
24 min_row_limit = min(min_row_limit, row_limit)
25 min_col_limit = min(min_col_limit, col_limit)
26
27 # The area of the intersection rectangle contains all maximum values
28 return min_row_limit * min_col_limit
29
1class Solution {
2 /**
3 * Finds the count of maximum elements in a matrix after applying operations.
4 * Each operation increments all elements in a submatrix from (0,0) to (ai-1, bi-1).
5 * The maximum elements will be in the intersection of all operation ranges.
6 *
7 * @param m Initial number of rows in the matrix
8 * @param n Initial number of columns in the matrix
9 * @param ops Array of operations, where ops[i] = [ai, bi] defines the submatrix size
10 * @return The count of maximum elements after all operations
11 */
12 public int maxCount(int m, int n, int[][] ops) {
13 // Find the minimum row and column bounds across all operations
14 // The intersection area will contain the maximum values
15 for (int[] operation : ops) {
16 // Update m to be the minimum row boundary
17 m = Math.min(m, operation[0]);
18 // Update n to be the minimum column boundary
19 n = Math.min(n, operation[1]);
20 }
21
22 // Return the area of the intersection (minimum row * minimum column)
23 // This represents the count of maximum elements
24 return m * n;
25 }
26}
27
1class Solution {
2public:
3 int maxCount(int m, int n, vector<vector<int>>& ops) {
4 // Find the minimum dimensions that all operations cover
5 // Each operation increments a rectangle from (0,0) to (ops[i][0]-1, ops[i][1]-1)
6 // The overlap of all operations is the rectangle with minimum dimensions
7
8 // Iterate through all operations to find the minimum row and column bounds
9 for (const auto& operation : ops) {
10 // Update m to be the minimum row bound across all operations
11 m = min(m, operation[0]);
12 // Update n to be the minimum column bound across all operations
13 n = min(n, operation[1]);
14 }
15
16 // Return the area of the smallest rectangle that all operations cover
17 // This represents the count of cells with the maximum value
18 return m * n;
19 }
20};
21
1/**
2 * Finds the maximum count of integers that appear in the smallest rectangle
3 * after applying all operations on an m x n matrix.
4 * Each operation ops[i] = [ai, bi] increments all elements in the rectangle
5 * from (0, 0) to (ai-1, bi-1).
6 *
7 * @param m - The number of rows in the matrix
8 * @param n - The number of columns in the matrix
9 * @param ops - Array of operations, where each operation is [rowLimit, colLimit]
10 * @returns The count of maximum integers in the resulting matrix
11 */
12function maxCount(m: number, n: number, ops: number[][]): number {
13 // Find the intersection of all operation rectangles
14 // The smallest rectangle will contain the maximum values
15 for (const [rowLimit, colLimit] of ops) {
16 // Update m to be the minimum row limit across all operations
17 m = Math.min(m, rowLimit);
18 // Update n to be the minimum column limit across all operations
19 n = Math.min(n, colLimit);
20 }
21
22 // The area of the smallest rectangle gives us the count of maximum integers
23 return m * n;
24}
25
Time and Space Complexity
The time complexity is O(k)
, where k
is the length of the operations array ops
. This is because the algorithm iterates through the ops
list exactly once, performing constant-time operations (minimum comparisons and assignments) for each operation pair [a, b]
.
The space complexity is O(1)
. The algorithm only uses two variables m
and n
to track the minimum dimensions, which are modified in place. No additional data structures are created that scale with the input size, resulting in constant space usage.
Learn more about how to find time and space complexity quickly.
Common Pitfalls
1. Misunderstanding the Operation Indices
A common mistake is confusing the operation parameters [ai, bi]
with the actual cell indices. The operation [ai, bi]
affects cells from (0, 0)
to (ai-1, bi-1)
inclusive, meaning it covers ai
rows and bi
columns, not the cell at position (ai, bi)
.
Incorrect interpretation:
# Wrong: Thinking [2, 2] only affects cell at position (2, 2) # or affects cells from (0, 0) to (2, 2) which would be 3x3
Correct understanding:
# Right: [2, 2] affects cells from (0, 0) to (1, 1), which is a 2x2 area
2. Handling Empty Operations Array Incorrectly
Some implementations might not properly handle the case when ops
is empty, potentially returning 0 or causing an error.
Problematic approach:
def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
if not ops:
return 0 # Wrong! Should return m * n
min_row = float('inf')
min_col = float('inf')
for a, b in ops:
min_row = min(min_row, a)
min_col = min(min_col, b)
return min_row * min_col # This would return inf * inf if ops is empty
Correct approach:
def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
min_row = m # Initialize with matrix dimensions
min_col = n
for a, b in ops:
min_row = min(min_row, a)
min_col = min(min_col, b)
return min_row * min_col # Returns m * n when ops is empty
3. Actually Creating the Matrix
A significant inefficiency is actually creating and updating the matrix when you only need to find the intersection area.
Inefficient approach:
def maxCount(self, m: int, n: int, ops: List[List[int]]) -> int:
# Unnecessarily creates and modifies the entire matrix
matrix = [[0] * n for _ in range(m)]
for a, b in ops:
for i in range(a):
for j in range(b):
matrix[i][j] += 1
# Then counts maximum values
max_val = max(max(row) for row in matrix)
return sum(1 for row in matrix for val in row if val == max_val)
This approach has O(mnk) time complexity and O(m*n) space complexity, where k is the number of operations, making it inefficient for large matrices.
4. Off-by-One Errors with Boundaries
Confusion about whether the operation boundaries are inclusive or exclusive can lead to errors.
Potential mistake:
# Thinking you need to subtract 1 from the result return (min_row - 1) * (min_col - 1) # Wrong!
The operation [ai, bi]
already represents the count of rows and columns (ai rows from 0 to ai-1), so no adjustment is needed in the final calculation.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]
?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
8
1public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
12
1class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85
Recommended Readings
Math for Technical Interviews How much math do I need to know for technical interviews The short answer is about high school level math Computer science is often associated with math and some universities even place their computer science department under the math faculty However the reality is that you
Coding Interview Patterns Your Personal Dijkstra's Algorithm to Landing Your Dream Job The goal of AlgoMonster is to help you get a job in the shortest amount of time possible in a data driven way We compiled datasets of tech interview problems and broke them down by patterns This way
Recursion Recursion is one of the most important concepts in computer science Simply speaking recursion is the process of a function calling itself Using a real life analogy imagine a scenario where you invite your friends to lunch https assets algo monster recursion jpg You first call Ben and ask
Want a Structured Path to Master System Design Too? Don’t Miss This!