209. Range Sum Query 2D - Immutable

PRO

Medium

Topics

Companies

Hint

Understand Before Coding

Visualize This Problem

Open Visualizer

Draw Your Approach

Draw

Example 1:

Input:

matrix = [[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]], row1 = 2, col1 = 1, row2 = 4, col2 = 3

Output: 8

Explanation: The sum of elements in the red rectangle (from original matrix indices (2,1) to (4,3)) is: matrix[2][1] + matrix[2][2] + matrix[2][3] + matrix[3][1] + matrix[3][2] + matrix[3][3] + matrix[4][1] + matrix[4][2] + matrix[4][3] = 2 + 0 + 1 + 1 + 0 + 1 + 0 + 3 + 0 = 8.

Example 2:

Input:

matrix = [[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]], row1 = 1, col1 = 1, row2 = 2, col2 = 2

Output: 11

Explanation: The sum of elements in the green rectangle (from original matrix indices (1,1) to (2,2)) is: matrix[1][1] + matrix[1][2] + matrix[2][1] + matrix[2][2] = 6 + 3 + 2 + 0 = 11.

Example 3:

Input:

matrix = [[3, 0, 1, 4, 2], [5, 6, 3, 2, 1], [1, 2, 0, 1, 5], [4, 1, 0, 1, 7], [1, 0, 3, 0, 5]], row1 = 1, col1 = 2, row2 = 2, col2 = 4

Output: 12

Explanation: The sum of elements in the blue rectangle (from original matrix indices (1,2) to (2,4)) is: matrix[1][2] + matrix[1][3] + matrix[1][4] + matrix[2][2] + matrix[2][3] + matrix[2][4] = 3 + 2 + 1 + 0 + 1 + 5 = 12.

Constraints:

•
•
•
•
•
•
•

Time Complexity

N/A

Space Complexity

N/A

209. Range Sum Query 2D - Immutable

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Example 3:

Constraints:

Learn

Topics

Companies

Hint

Use Cases

209. Range Sum Query 2D - Immutable

Understand Before Coding

Visualize This Problem

Draw Your Approach

Example 1:

Example 2:

Example 3:

Constraints:

Learn

Topics

Companies

Hint

Use Cases