Range Addition II - Practice Coding Problems

Range Addition II - Problem

Array Math Easy

You are given an m x n matrix M initialized with all 0's and an array of operations ops, where ops[i] = [a_i, b_i] means M[x][y] should be incremented by one for all 0 ≤ x < a_i and 0 ≤ y < b_i.

Count and return the number of maximum integers in the matrix after performing all the operations.

Input & Output

Example 1 — Basic Operations

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

› Output: 4

💡 Note: Operation [2,2] increments cells (0,0), (0,1), (1,0), (1,1). Operation [3,3] increments all 9 cells. The intersection (0,0), (0,1), (1,0), (1,1) gets incremented twice, so 4 cells have maximum value.

Example 2 — Empty Operations

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

› Output: 9

💡 Note: No operations means all cells remain 0. All 9 cells have the same maximum value of 0.

Example 3 — Single Cell Intersection

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

› Output: 1

💡 Note: The intersection of all operations is min(2,3,1) × min(2,3,1) = 1×1. Only cell (0,0) receives all increments.

Constraints

1 ≤ m, n ≤ 4 × 10⁴
0 ≤ ops.length ≤ 10⁴
ops[i].length == 2
1 ≤ a_i ≤ m
1 ≤ b_i ≤ n

Visualization

Tap to expand

Understanding the Visualization

Input Matrix

3×3 matrix with operations [[2,2],[3,3]]

Apply Operations

Each operation increments a rectangle from top-left

Find Maximum Count

Count cells with highest increment value

Key Takeaway

🎯 Key Insight: Maximum values only exist in the intersection of all operation rectangles

Asked in

G Google 25 a Amazon 15 M Microsoft 20

The key insight is that maximum values only occur in the intersection of all operation rectangles. We find the minimum dimensions across all operations to determine this intersection area. Best approach uses mathematical optimization in O(k) time and O(1) space.

Common Approaches

Approach	Time	Space	Notes
✓ Mathematical Optimization	O(k)	O(1)	Find intersection rectangle without building matrix
Brute Force Matrix Simulation	O(k × a × b)	O(m × n)	Create actual matrix and simulate all operations

Mathematical Optimization — Algorithm Steps

Step 1: Handle empty operations case (return m×n)
Step 2: Find minimum width and height across all operations
Step 3: Return area of intersection rectangle

Visualization

Tap to expand

Step-by-Step Walkthrough

Operations

ops = [[2,2],[3,3]] on 3×3 matrix

Find Intersection

min(2,3) = 2 for both dimensions

Calculate Area

2×2 = 4 cells have maximum value

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <limits.h>

int min(int a, int b) {
    return a < b ? a : b;
}

int solution(int m, int n, int ops[][2], int opsSize) {
    // If no operations, all cells have value 0
    if (opsSize == 0) {
        return m * n;
    }
    
    // Find intersection rectangle
    int minA = INT_MAX;
    int minB = INT_MAX;
    
    for (int i = 0; i < opsSize; i++) {
        if (ops[i][0] < minA) minA = ops[i][0];
        if (ops[i][1] < minB) minB = ops[i][1];
    }
    
    // Intersection cannot exceed matrix bounds
    minA = min(minA, m);
    minB = min(minB, n);
    
    return minA * minB;
}

int main() {
    int m, n;
    scanf("%d", &m);
    scanf("%d", &n);
    
    char line[10000];
    scanf(" %[^\n]", line);
    
    // Simple parsing for operations
    int ops[1000][2];
    int opsSize = 0;
    
    if (strcmp(line, "[]") != 0) {
        char* ptr = line + 1; // skip opening [
        while (*ptr && *ptr != ']') {
            if (*ptr == '[') {
                ptr++;
                ops[opsSize][0] = atoi(ptr);
                while (*ptr && *ptr != ',') ptr++;
                ptr++; // skip comma
                ops[opsSize][1] = atoi(ptr);
                opsSize++;
                while (*ptr && *ptr != ']') ptr++;
                ptr++; // skip ]
            } else {
                ptr++;
            }
        }
    }
    
    int result = solution(m, n, ops, opsSize);
    printf("%d\n", result);
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(k)

Single pass through k operations to find minimums

✓ Linear Growth

Space Complexity

O(1)

Only storing min values, no matrix needed

✓ Linear Space

32.0K Views

Medium Frequency

~15 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Mathematical Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler