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 sumRegion() 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 sumRegion() function:

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

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

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

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

Output

The output of the sumRegion() 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:

  • class NumMatrix(var users1: Array[Array[Int]]) : This method initializes the object with the integer matrix, matrix.

  • def sumRegion(row1: Int, col1: Int, row2: Int, col2: Int): Int: 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.