Matrix Block Sum

Easy

0/40

Contributed by

0 upvote

Asked in company

Problem statement

You are given a 2D integer matrix (an array of arrays). Your task is to efficiently calculate the sum of elements within a specific rectangular block of this matrix.

The rectangular block is defined by its top-left corner at (r1, c1) and its bottom-right corner at (r2, c2). You need to find the sum of all elements matrix[i][j] such that r1 <= i <= r2 and c1 <= j <= c2.

Detailed explanation ( Input/output format, Notes, Images )

Input Format:

The first line contains two space-separated integers: R (number of rows) and C (number of columns) in the matrix.

The next R lines each contain C space-separated integers, representing the rows of the matrix.

The final line contains four space-separated integers: r1, c1, r2, c2, representing the 0-indexed coordinates of the top-left and bottom-right corners of the target rectangle.

Output Format:

The output should be a single integer representing the sum of all elements within the specified rectangle.

Note:

The matrix coordinates are 0-indexed.

The rectangle's boundaries (r1, c1, r2, c2) are inclusive.

The sum can be large, so be mindful of potential integer overflow.

Sample Input 1:

Sample Output 1:

Explanation for Sample 1:

The matrix is:

 1  2  3  4
 5  6  7  8
 9 10 11 12

The query rectangle is from (r1, c1) = (1, 1) to (r2, c2) = (2, 2). The elements in this rectangle are:

6  7
10 11
=> The sum is 6 + 7 + 10 + 11 = 34.

Expected Time Complexity:

The expected time complexity for a single query is O(1) after an initial O(R * C) pre-computation. The total complexity is O(R * C).

Constraints:

1 <= R, C <= 1000
-10^9 <= matrix[i][j] <= 10^9
0 <= r1 <= r2 < R
0 <= c1 <= c2 < C

Time limit: 1 sec

Approaches (1)

Approach 1

2D Prefix Sum

Time Complexity

Space Complexity

(100% EXP penalty)

Matrix Block Sum

Console