Range Addition II

Easy
1123.

Range Addition II

Range Addition II is an easy coding problem on arrays and math, asked in Amazon and Google interviews.

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^4
  • 0 <= ops.length <= 10^4
  • ops[i].length == 2
  • 1 <= a <= m
  • 1 <= b <= n
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number} m
 * @param {number} n
 * @param {number[][]} ops
 * @return {number}
 */
var maxCount = function(m, n, ops) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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^4
  • 0 <= ops.length <= 10^4
  • ops[i].length == 2
  • 1 <= a <= m
  • 1 <= b <= n

Hints for Range Addition II

  1. Hint 1

    Every operation includes the cell (0, 0), so that cell always reaches the maximum.

  2. Hint 2

    A cell holds the maximum exactly when every operation covers it.

  3. Hint 3

    The cells covered by all operations form the top-left minA x minB block.

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

  1. Set minA = m and minB = n.
  2. For each operation [a, b], lower minA to a and minB to b when smaller.
  3. 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 is m * n, not 0.
  • m * n reaches 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 * n

Java

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