Range Addition II — Solution in Python, Java & C++
Range Addition II solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem on arrays and math.
Range Addition II is an easy coding problem on arrays and math, asked in Amazon and Google interviews.
- Difficulty: Easy
- Topics: Arrays, Math
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Start with an m x n matrix M of zeros. Each operation ops[i] = [a, b] adds 1 to every cell M[x][y] with 0 <= x < a and 0 <= y < b — the top-left a x b block.
After performing all operations, return how many cells hold the maximum value in the matrix.
Example 1
Input: m = 4, n = 5, ops = [[3,4],[2,5],[4,2]]
Output: 4
Explanation: Only the top-left 2 x 2 block is inside all three operations, so its 4 cells hold the maximum, 3.
Example 2
Input: m = 3, n = 3, ops = []
Output: 9
Explanation: With no operations every cell is 0, the maximum.
Example 3
Input: m = 6, n = 2, ops = [[6,1]]
Output: 6
Constraints
1 <= m, n <= 4 * 10^40 <= ops.length <= 10^4ops[i].length == 21 <= a <= m1 <= b <= n
Hints for Range Addition II
Hint 1
Every operation includes the cell
(0, 0), so that cell always reaches the maximum.Hint 2
A cell holds the maximum exactly when every operation covers it.
Hint 3
The cells covered by all operations form the top-left
minA x minBblock.
How to solve Range Addition II
All operations are top-left blocks, so their common part is again a top-left block: min(a) rows by min(b) columns. Those cells are incremented by every operation, and no other cell is.
Approach
- Set
minA = mandminB = n. - For each operation
[a, b], lowerminAtoaandminBtobwhen smaller. - Return
minA * minB.
Why it works
Cell (x, y) is incremented by operation [a, b] exactly when x < a and y < b. It is incremented by every operation exactly when x < minA and y < minB, and cell (0, 0) shows that the maximum equals the number of operations. So the cells holding the maximum are precisely the minA x minB block — and with no operations, the whole matrix.
Complexity
- Time —
O(k) for k operations - Space —
O(1)
Pitfalls
- Do not build the matrix — it can have 1.6 × 10^9 cells.
- With an empty
ops, the answer ism * n, not 0. m * nreaches 1.6 × 10^9, which still fits a signed 32-bit int (the limit is about 2.1 × 10^9).
Reference solution
Python
from typing import List
def maxCount(m: int, n: int, ops: List[List[int]]) -> int:
for a, b in ops:
m = min(m, a)
n = min(n, b)
return m * nJava
public static int maxCount(int m, int n, int[][] ops) {
for (int[] op : ops) {
m = Math.min(m, op[0]);
n = Math.min(n, op[1]);
}
return m * n;
}C++
int maxCount(int m, int n, vector<vector<int>>& ops) {
for (auto& op : ops) {
m = min(m, op[0]);
n = min(n, op[1]);
}
return m * n;
}JavaScript
var maxCount = function(m, n, ops) {
for (var i = 0; i < ops.length; i++) {
m = Math.min(m, ops[i][0]);
n = Math.min(n, ops[i][1]);
}
return m * n;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays