Increment Submatrices by One - Practice Coding Problems

Increment Submatrices by One - Problem

You are given a positive integer n, indicating that we initially have an n x n 0-indexed integer matrix mat filled with zeroes.

You are also given a 2D integer array query. For each query[i] = [row1i, col1i, row2i, col2i], you should do the following operation:

Add 1 to every element in the submatrix with the top left corner (row1i, col1i) and the bottom right corner (row2i, col2i). That is, add 1 to mat[x][y] for all row1i <= x <= row2i and col1i <= y <= col2i.

Return the matrix mat after performing every query.

Input & Output

Example 1 — Basic Rectangle Update

$ Input: n = 3, queries = [[1,1,2,2]]

› Output: [[0,0,0],[0,1,1],[0,1,1]]

💡 Note: Start with 3×3 zero matrix. Query [1,1,2,2] increments submatrix from (1,1) to (2,2), so cells [1,1], [1,2], [2,1], [2,2] become 1.

Example 2 — Multiple Overlapping Queries

$ Input: n = 2, queries = [[0,0,1,1],[0,0,0,0]]

› Output: [[2,1],[1,1]]

💡 Note: First query increments entire 2×2 matrix. Second query increments only cell (0,0). Final: (0,0) has value 2, others have value 1.

Example 3 — Single Cell Update

$ Input: n = 2, queries = [[1,1,1,1]]

› Output: [[0,0],[0,1]]

💡 Note: Query targets only cell (1,1), incrementing it from 0 to 1. All other cells remain 0.

Constraints

1 ≤ n ≤ 500
1 ≤ queries.length ≤ 10⁴
queries[i].length == 4
0 ≤ row1_i ≤ row2_i < n
0 ≤ col1_i ≤ col2_i < n

Visualization

Tap to expand

Understanding the Visualization

Input

3×3 zero matrix and query [1,1,2,2]

Process

Increment rectangle from (1,1) to (2,2)

Output

Matrix with 2×2 submatrix incremented

Key Takeaway

🎯 Key Insight: Use difference arrays to mark boundaries efficiently rather than updating every cell individually

Asked in

G Google 15 a Amazon 12 M Microsoft 8 f Facebook 6

The key insight is to use a 2D difference array to mark rectangle boundaries instead of updating every cell. The optimal approach uses difference arrays to mark boundaries in O(1) per query, then computes 2D prefix sums to get final values. Time: O(q + n²), Space: O(n²)

Common Approaches

Approach	Time	Space	Notes
✓ 2D Difference Array	O(q + n²)	O(n²)	Use 2D difference array to mark rectangle boundaries, then compute prefix sums
Brute Force	O(q × n²)	O(n²)	For each query, iterate through the submatrix and increment each cell by 1

2D Difference Array — Algorithm Steps

Create a difference array to mark rectangle boundaries
For each query, update only 4 corner positions
Compute 2D prefix sum to get final matrix

Visualization

Tap to expand

Step-by-Step Walkthrough

Mark Boundaries

Add/subtract at rectangle corners in difference array

Compute Prefix Sum

Calculate cumulative sums in 2D

Final Result

Get final matrix values

Code -

solution.c — C

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

int** solution(int n, int** queries, int queryCount) {
    // Create difference array
    int** diff = (int**)malloc((n + 1) * sizeof(int*));
    for (int i = 0; i <= n; i++) {
        diff[i] = (int*)calloc(n + 1, sizeof(int));
    }
    
    // Process each query using difference array technique
    for (int q = 0; q < queryCount; q++) {
        int row1 = queries[q][0], col1 = queries[q][1];
        int row2 = queries[q][2], col2 = queries[q][3];
        diff[row1][col1] += 1;
        diff[row1][col2 + 1] -= 1;
        diff[row2 + 1][col1] -= 1;
        diff[row2 + 1][col2 + 1] += 1;
    }
    
    // Build result matrix using 2D prefix sum
    int** result = (int**)malloc(n * sizeof(int*));
    for (int i = 0; i < n; i++) {
        result[i] = (int*)calloc(n, sizeof(int));
    }
    
    for (int i = 0; i < n; i++) {
        for (int j = 0; j < n; j++) {
            result[i][j] = diff[i][j];
            if (i > 0) result[i][j] += result[i-1][j];
            if (j > 0) result[i][j] += result[i][j-1];
            if (i > 0 && j > 0) result[i][j] -= result[i-1][j-1];
        }
    }
    
    return result;
}

int main() {
    int n;
    scanf("%d", &n);
    
    // Simplified for demo
    int queryCount = 1;
    int** queries = (int**)malloc(queryCount * sizeof(int*));
    
    int** result = solution(n, queries, queryCount);
    
    printf("[");
    for (int i = 0; i < n; i++) {
        printf("[");
        for (int j = 0; j < n; j++) {
            printf("%d", result[i][j]);
            if (j < n - 1) printf(",");
        }
        printf("]");
        if (i < n - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(q + n²)

O(q) to process queries plus O(n²) to compute final prefix sums

⚠ Quadratic Growth

Space Complexity

O(n²)

Need difference array and result matrix, both n×n

⚠ Quadratic Space

23.4K Views

Medium Frequency

~25 min Avg. Time

892 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

2D Difference Array — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler