Skip to main content
Talentd

Range Addition II - Solution & Explanation

EasyArrayMath17 min readAsked at: Amazon, Bloomberg, Ixl
Practice this problem

Problem Statement

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

Approach Overview

Problem Overview: You start with an m x n matrix filled with zeros. Each operation [a, b] increments every cell in the submatrix from (0,0) to (a-1,b-1). After applying all operations, the task is to count how many cells contain the maximum value in the matrix.

Approach 1: Minimize Rows and Columns (O(k) time, O(1) space)

The key observation is that every operation increments a rectangle starting from the top-left corner. The cells that end up with the largest value are the ones included in all operations. That overlapping region is determined by the smallest row boundary and the smallest column boundary across all operations. Iterate through the operations, track minRow = min(minRow, a) and minCol = min(minCol, b). The number of cells with the maximum value becomes minRow * minCol. This works because each operation overlaps in the top-left region, and the tightest bounds define the common intersection. Time complexity is O(k) where k is the number of operations, and space complexity is O(1). This approach mainly relies on simple iteration over an array of operations and basic math reasoning.

Approach 2: Direct Simulation (Less Efficient) (O(k * m * n) time, O(m * n) space)

A straightforward method is to simulate the process exactly as described. Create an m x n matrix initialized with zeros. For each operation [a, b], iterate through rows 0..a-1 and columns 0..b-1 and increment each cell. After processing all operations, scan the matrix to find the maximum value and count how many cells contain it. While easy to implement, this approach performs unnecessary repeated work since many cells are incremented multiple times across operations. The time complexity grows to O(k * m * n) with O(m * n) space, which becomes inefficient for larger matrices.

Recommended for interviews: The minimize rows and columns approach is the expected solution. It shows you recognize the overlapping rectangle pattern rather than simulating updates. Starting with the direct simulation demonstrates understanding of the problem mechanics, but identifying the intersection of all operations and reducing the solution to minRow * minCol demonstrates strong problem-solving skills and comfort with array traversal and simple mathematical reasoning.

Approach 1: Approach 1: Minimize Rows and Columns

To solve this problem efficiently, observe that each operation affects a submatrix starting from the top-left corner. Thus, the final result of the operations is determined by the smallest intersected submatrix affected by all operations. Find the minimum value of "a" and "b" from all operations in ops. This will give you the dimensions of the area where the maximum integers will exist after applying all operations.

The key insight is that the size of the submatrix affected by all operations determines the count of maximum numbers in the final matrix.

This solution iterates over all operations provided and finds the minimum values of rows and columns from the operations. These minimums define the dimensions of the submatrix that will have the maximum value after all operations. We simply calculate the area of this submatrix to get the count of maximum integers.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(k), where k is the number of operations.

Space Complexity: O(1), as we are using only a few extra variables.

Try this approach in the editor →

Approach 2: Approach 2: Direct Simulation (Less Efficient)

This approach simulates the operations directly on the matrix. For each operation, we iterate through the specified submatrix and increment the values. Finally, we determine the number of times the maximum value occurs in the matrix. Although this method is less efficient due to its higher computational cost, it reinforces understanding of the problem.

This solution creates a matrix of size m x n and sets all values to zero. For each operation, it increments the values within the specified submatrix. After processing all operations, it finds the maximum value in the matrix and counts its occurrences.

Code

CC++JavaPythonC#JavaScript

C

C++

Java

Python

C#

JavaScript

Complexity

Time Complexity: O(m * n * k), where m and n are the dimensions of the matrix, and k is the number of operations.

Space Complexity: O(m * n), for the matrix.

Try this approach in the editor →

Approach 3: Brain Teaser

We notice that the intersection of all operation submatrices is the submatrix where the final maximum integer is located, and each operation submatrix starts from the top-left corner (0, 0). Therefore, we traverse all operation submatrices to find the minimum number of rows and columns. Finally, we return the product of these two values.

Note that if the operation array is empty, the number of maximum integers in the matrix is m times n.

The time complexity is O(k), where k is the length of the operation array ops. The space complexity is O(1).

Code

PythonJavaC++GoTypeScriptRustJavaScript

Python

Java

C++

Go

TypeScript

Rust

JavaScript

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Approach 1: Minimize Rows and Columns

Time Complexity: O(k), where k is the number of operations.

Space Complexity: O(1), as we are using only a few extra variables.

Approach 2: Direct Simulation (Less Efficient)

Time Complexity: O(m * n * k), where m and n are the dimensions of the matrix, and k is the number of operations.

Space Complexity: O(m * n), for the matrix.

Brain Teaser—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Minimize Rows and ColumnsO(k)O(1)Best approach for interviews and production. Uses the intersection of all operations.
Direct SimulationO(k * m * n)O(m * n)Useful for understanding the problem or when constraints are extremely small.

Video Solution

Range Addition II Leetcode 598 | Live coding session 🔥🔥🔥 • Coding Decoded • 3,056 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Range Addition II easy or hard?
Range Addition II is classified as an Easy problem on LeetCode with an acceptance rate above 50%. The challenge is recognizing the overlapping rectangle insight instead of simulating the matrix updates.
Range Addition II Python/Java solution
In Python or Java, iterate through the operations list and keep updating two variables: minRow and minCol. Initialize them with m and n, update using min(minRow, a) and min(minCol, b) for each operation, and return minRow * minCol. The logic is identical across Python, Java, C++, and JavaScript.
How to solve Range Addition II in O(n)?
Treat n as the number of operations. Iterate through the operations list and track the minimum values of a and b. These values define the intersection rectangle that gets incremented in every operation. The final answer is simply minRow multiplied by minCol, giving an O(n) time and O(1) space solution.
What is the best approach for Range Addition II?
The optimal approach tracks the smallest row and column limits across all operations. Since each operation increments a rectangle from the top-left corner, the cells with the maximum value lie in the overlapping region of all operations. Computing minRow and minCol gives the intersection size, and the result is minRow * minCol. This runs in O(k) time with O(1) space.
Is Range Addition II asked at Google/Amazon/Meta?
Range Addition II represents a common interview pattern involving overlapping ranges and matrix updates. Variations of this idea appear in interviews at large tech companies including Amazon and Google, especially when testing optimization skills and recognizing patterns that avoid brute-force simulation.
What data structure is used in Range Addition II?
The problem mainly uses arrays to store the list of operations. The optimal solution does not require constructing the matrix and instead relies on tracking minimum boundaries using simple variables and mathematical reasoning.
What is the time complexity of Range Addition II?
The optimal solution runs in O(k) time where k is the number of operations. It only scans the operations once to compute the minimum row and column boundaries. A brute-force simulation approach takes O(k * m * n) time because every operation updates many cells in the matrix.

Ready to solve this problem?

Practice Range Addition II with our built-in code editor and test cases.

Practice on FleetCode
Previous

Range Addition

Next

Sum of Matrix After Queries