Range Sum Query 2D - Immutable

Range Sum Query 2D - Immutable is a Medium Data Structures and Algorithms interview problem you can solve, run and submit on Thita.ai. It belongs to the Array/Matrix Manipulation Patterns pattern, in the Prefix Sum - Subarray Sum / Range Query subpattern.

Problem statement

Implement a class named NumMatrix for an integer matrix that remains unchanged after construction. If the matrix has m rows and n columns, rows are numbered from 0 to m - 1 and columns from 0 to n - 1.

The constructor NumMatrix(matrix) receives the matrix and may preprocess it. The method sumRegion(row1, col1, row2, col2) identifies the inclusive rectangular region whose top-left cell is (row1, col1) and whose bottom-right cell is (row2, col2).

Return the sum of all values in that region. There are no update operations, and every call to sumRegion must run in O(1) time.

The JSON test format contains exactly two keys: operations and arguments. The first operation is NumMatrix; each remaining operation is sumRegion. Return a JSON array with null for the constructor and the integer result for each query.

Example 1:

Input:

["NumMatrix", "sumRegion", "sumRegion", "sumRegion"] [[[[8,-2,5],[1,7,-4],[-3,6,0]]],[0,1,1,2],[1,0,2,1],[2,2,2,2]]

Output:

[null,6,11,0]

Explanation: The first rectangle contains -2, 5, 7, and -4, which sum to 6. The second sums to 11, and the final query selects the single cell containing 0.

Example 2:

Input:

["NumMatrix", "sumRegion", "sumRegion", "sumRegion"] [[[[-6],[10],[4],[-1]]],[0,0,3,0],[1,0,2,0],[3,0,3,0]]

Output:

[null,7,14,-1]

Explanation: Because the matrix has one column, each query sums a contiguous section of that column. The full column totals 7, while the middle section totals 14.

Example 3:

Input:

["NumMatrix", "sumRegion", "sumRegion", "sumRegion"] [[[[12,-5],[-7,9]]],[0,0,1,1],[0,0,1,0],[0,1,1,1]]

Output:

[null,9,5,4]

Explanation: The whole matrix sums to 9. Its first column sums to 5 and its second column sums to 4.

Constraints:

- 1 <= matrix.length <= 200 - 1 <= matrix[i].length <= 200 - All rows in matrix have the same length - -10^4 <= matrix[i][j] <= 10^4 - The first operation is NumMatrix and every later operation is sumRegion - 0 <= row1 <= row2 < m - 0 <= col1 <= col2 < n

Topics and companies

Topics: Array, Matrix, Prefix Sum, Design.

How to practise Range Sum Query 2D - Immutable on Thita.ai

Starter code is provided in C#, C++, Go, Java, JavaScript and Python. Your solution runs against 5 test cases for this problem, with the AI coach available for a hint when you are stuck rather than a finished answer. The reference solution runs in O(mn) preprocessing and O(1) per sumRegion query time and O(mn) space.

Open Range Sum Query 2D - Immutable in the code editor, or read the Range Sum Query 2D - Immutable editorial for a worked solution with its approach and complexity analysis.

Where Range Sum Query 2D - Immutable sits in the DSA pattern sheet

Problems related to Range Sum Query 2D - Immutable

Other problems that use the same Prefix Sum - Subarray Sum / Range Query and Array/Matrix Manipulation Patterns techniques:

Preparing this workspace.