DIY: Range Sum Query 2D — Immutable

Solve the interview question "Range Sum Query 2D — Immutable" in this lesson.

Problem statement

Given an m * n matrix, you need to handle multiple queries of the following type:

Calculate the sum of the elements of the matrix inside the rectangle defined by its upper left corner, (row1,col1)(row1, col1), and lower right corner, (row2,col2)(row2, col2).

Constraints

You can assume the following constraints for this problem:

  • m == matrix.length
  • n == matrix[i].length
  • 1 <= m, n <= 200
  • -105 <= matrix[i][j] <= 105
  • 0 <= row1 <= row2 < m
  • 0 <= col1 <= col2 < n

Input

The NumMatrix class constructor takes the matrix as the input. The sum_region() function takes the four integer inputs that represent the starting and ending coordinates of the sub-region. Here is an example of the consecutive inputs to the sum_region() function:

numMatrix = NumMatrix(
[
  [1, 3, 5],
  [2, 4, 6],
  [7, 8, 2],
  [9, 3, 6]
])

// Example - 1
numMatrix.sum_region(0, 0, 2, 2)

// Example - 2
numMatrix.sum_region(0, 1, 3, 2)

// Example - 3
numMatrix.sum_region(2, 1, 3, 1)

Output

The output of the sum_region() function is an integer that represents the region’s sum. Here is an example of the output:

// Example - 1
38

// Example - 2
37

// Example - 3
11

Coding exercise

You need to implement the NumMatrix class, whose skeleton is provided in the code playground below. You will need to implement the following methods:

  • new(matrix: Vec<Vec<i32>>): This method initializes the object with the integer matrix, matrix.

  • sum_region(int row1, int col1, int row2, int col2)-> i32: This method returns the sum of the elements of the matrix inside the rectangle defined by its upper left corner, (row1,col1)(row1, col1), and lower right corner, (row2,col2)(row2, col2).

Level up your interview prep. Join Educative to access 70+ hands-on prep courses.