Range Sum Query 2D Immutable

                                            
class NumMatrix {
public:
    NumMatrix(vector<vector<int>>& matrix) {
        if (matrix.empty() || matrix[0].empty()) return;
        dp = vector<vector<int>>(matrix.size() + 1, vector<int>(matrix[0].size() + 1, 0));
        for (int i = 1; i <= matrix.size(); i++) {
            for (int j = 1; j <= matrix[0].size(); j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
    }

private:
    vector<vector<int>> dp;
};
/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix* obj = new NumMatrix(matrix);
 * int param_1 = obj->sumRegion(row1,col1,row2,col2);
 */

                                            
class NumMatrix {
    int[][] dp;

    public NumMatrix(int[][] matrix) {
        if (matrix == null || matrix.length == 0 || matrix[0].length == 0) {
            return;
        }
        int m = matrix.length;
        int n = matrix[0].length;
        dp = new int[m + 1][n + 1];
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                dp[i][j] = dp[i - 1][j] + dp[i][j - 1] - dp[i - 1][j - 1] + matrix[i - 1][j - 1];
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1];
    }
}
/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

                                            
class NumMatrix(object):
    def __init__(self, matrix):
        if not matrix:
            return
        m, n = len(matrix), len(matrix[0])
        self.dp = [[0] * (n + 1) for _ in range(m + 1)]
        for i in range(1, m + 1):
            for j in range(1, n + 1):
                self.dp[i][j] = matrix[i - 1][j - 1] + self.dp[i - 1][j] + self.dp[i][j - 1] - self.dp[i - 1][j - 1]

    def sumRegion(self, row1, col1, row2, col2):
        return self.dp[row2 + 1][col2 + 1] - self.dp[row2 + 1][col1] - self.dp[row1][col2 + 1] + self.dp[row1][col1]

                                            
/**
 * @param {number[][]} matrix
 */
var NumMatrix = function(matrix) {
    this.dp = [];
    for (let i = 0; i < matrix.length; i++) {
        this.dp[i] = [];
        for (let j = 0; j < matrix[0].length; j++) {
            if (i === 0 && j === 0) {
                this.dp[i][j] = matrix[i][j];
            } else if (i === 0) {
                this.dp[i][j] = this.dp[i][j - 1] + matrix[i][j];
            } else if (j === 0) {
                this.dp[i][j] = this.dp[i - 1][j] + matrix[i][j];
            } else {
                this.dp[i][j] = this.dp[i - 1][j] + this.dp[i][j - 1] - this.dp[i - 1][j - 1] + matrix[i][j];
            }
        }
    }
};

/** 
 * @param {number} row1 
 * @param {number} col1 
 * @param {number} row2 
 * @param {number} col2
 * @return {number}
 */
NumMatrix.prototype.sumRegion = function(row1, col1, row2, col2) {
    if (row1 === 0 && col1 === 0) {
        return this.dp[row2][col2];
    } else if (row1 === 0) {
        return this.dp[row2][col2] - this.dp[row2][col1 - 1];
    } else if (col1 === 0) {
        return this.dp[row2][col2] - this.dp[row1 - 1][col2];
    } else {
        return this.dp[row2][col2] - this.dp[row1 - 1][col2] - this.dp[row2][col1 - 1] + this.dp[row1 - 1][col1 - 1];
    }
};

                                            
class NumMatrix {
    private $dp = [];

    /**
     * @param Integer[][] $matrix
     */
    function __construct($matrix) {
        $m = count($matrix);
        $n = count($matrix[0]);

        $this->dp = array_fill(0, $m + 1, array_fill(0, $n + 1, 0));

        for ($i = 1; $i <= $m; $i++) {
            for ($j = 1; $j <= $n; $j++) {
                $this->dp[$i][$j] = $this->dp[$i - 1][$j] + $this->dp[$i][$j - 1] - $this->dp[$i - 1][$j - 1] + $matrix[$i - 1][$j - 1];
            }
        }
    }

    /**
     * @param Integer $row1
     * @param Integer $col1
     * @param Integer $row2
     * @param Integer $col2
     * @return Integer
     */
    function sumRegion($row1, $col1, $row2, $col2) {
        return $this->dp[$row2 + 1][$col2 + 1] - $this->dp[$row1][$col2 + 1] - $this->dp[$row2 + 1][$col1] + $this->dp[$row1][$col1];
    }
}

                                            
class NumMatrix(matrix: Array<IntArray>) {
    private val dp = Array(matrix.size + 1) { IntArray(matrix[0].size + 1) }

    init {
        for (i in matrix.indices) {
            for (j in matrix[0].indices) {
                dp[i + 1][j + 1] = dp[i][j + 1] + dp[i + 1][j] - dp[i][j] + matrix[i][j]
            }
        }
    }

    fun sumRegion(row1: Int, col1: Int, row2: Int, col2: Int): Int {
        return dp[row2 + 1][col2 + 1] - dp[row1][col2 + 1] - dp[row2 + 1][col1] + dp[row1][col1]
    }
}
/**
 * Your NumMatrix object will be instantiated and called as such:
 * var obj = NumMatrix(matrix)
 * var param_1 = obj.sumRegion(row1,col1,row2,col2)
 */

                                            
class NumMatrix {
  late List<List<int>> _matrix;
  
  NumMatrix(List<List<int>> matrix) {
    _matrix = List<List<int>>.from(matrix);
    for (int i = 0; i < _matrix.length; i++) {
      for (int j = 1; j < _matrix[i].length; j++) {
        _matrix[i][j] += _matrix[i][j - 1];
      }
    }
  }
  
  int sumRegion(int row1, int col1, int row2, int col2) {
    int sum = 0;
    for (int i = row1; i <= row2; i++) {
      sum += _matrix[i][col2] - (col1 > 0 ? _matrix[i][col1 - 1] : 0);
    }
    return sum;
  }
}
/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = NumMatrix(matrix);
 * int param1 = obj.sumRegion(row1,col1,row2,col2);
*/

                                            
type NumMatrix struct {
    prefixSum [][]int
}

func Constructor(matrix [][]int) NumMatrix {
    m, n := len(matrix), len(matrix[0])
    prefixSum := make([][]int, m+1)
    for i := 0; i <= m; i++ {
        prefixSum[i] = make([]int, n+1)
    }
    for i := 1; i <= m; i++ {
        for j := 1; j <= n; j++ {
            prefixSum[i][j] = matrix[i-1][j-1] + prefixSum[i-1][j] + prefixSum[i][j-1] - prefixSum[i-1][j-1]
        }
    }
    return NumMatrix{prefixSum: prefixSum}
}

func (this *NumMatrix) SumRegion(row1 int, col1 int, row2 int, col2 int) int {
    return this.prefixSum[row2+1][col2+1] - this.prefixSum[row1][col2+1] - this.prefixSum[row2+1][col1] + this.prefixSum[row1][col1]
}

                                            
class NumMatrix(_matrix: Array[Array[Int]]) {
    private val dp: Array[Array[Int]] = {
        if (_matrix.isEmpty || _matrix(0).isEmpty) Array.ofDim[Int](0, 0)
        else {
            val m = _matrix.length
            val n = _matrix(0).length
            val dp = Array.ofDim[Int](m + 1, n + 1)
            for {
                i <- 1 to m
                j <- 1 to n
            } dp(i)(j) = dp(i - 1)(j) + dp(i)(j - 1) - dp(i - 1)(j - 1) + _matrix(i - 1)(j - 1)
            dp
        }
    }

    def sumRegion(row1: Int, col1: Int, row2: Int, col2: Int): Int = {
        dp(row2 + 1)(col2 + 1) - dp(row1)(col2 + 1) - dp(row2 + 1)(col1) + dp(row1)(col1)
    }
}
/**
 * Your NumMatrix object will be instantiated and called as such:
 * val obj = new NumMatrix(matrix)
 * val param_1 = obj.sumRegion(row1,col1,row2,col2)
 */

                                            
struct NumMatrix {
    prefix_sum: Vec<Vec<i32>>,
}

impl NumMatrix {
    fn new(matrix: Vec<Vec<i32>>) -> Self {
        let mut prefix_sum = vec![vec![0; matrix[0].len() + 1]; matrix.len() + 1];
        
        for i in 1..=matrix.len() {
            for j in 1..=matrix[0].len() {
                prefix_sum[i][j] = matrix[i - 1][j - 1] + prefix_sum[i - 1][j] + prefix_sum[i][j - 1] - prefix_sum[i - 1][j - 1];
            }
        }
        
        NumMatrix { prefix_sum }
    }
    
    fn sum_region(&self, row1: i32, col1: i32, row2: i32, col2: i32) -> i32 {
        let row1 = row1 as usize;
        let col1 = col1 as usize;
        let row2 = row2 as usize + 1;
        let col2 = col2 as usize + 1;
        
        self.prefix_sum[row2][col2] - self.prefix_sum[row2][col1] - self.prefix_sum[row1][col2] + self.prefix_sum[row1][col1]
    }
}

To solve this coding challenge, we need to create a class that can efficiently compute the sum of elements within a submatrix of a given 2D matrix. Here's a detailed methodology and pseudocode to accomplish this task.

Explanation

To achieve a solution where the sumRegion function works in O(1) time complexity, we can use a preprocessing step where we build a

dp

table (dynamic programming table) that holds the cumulative sums of submatrices. This preprocessing takes O(m * n) time, but querying any submatrix sum will be done in constant time. Here's the detailed thought process and explanation:

Initialization :

When initializing the
NumMatrix

object, we need to preprocess the matrix to set up our
dp

table. This table will store at each position
(i, j)

the sum of elements in the submatrix from the top-left corner
(0, 0)

to the position
(i, j)

.

Filling the
dp

Table :

We iterate over each element in the original matrix and use the values from neighboring cells in
dp

to compute the cumulative sum at each cell
(i, j)

.
The value at
dp[i][j]

is computed using the formula:

\text{dp}[i][j] = \text{matrix}[i-1][j-1] + \text{dp}[i-1][j] + \text{dp}[i][j-1] - \text{dp}[i-1][j-1]

This formula ensures that we add the current element and also account for the sums of submatrices ending at
(i-1, j)

,
(i, j-1)

and subtracts the overlapping submatrix ending at
(i-1, j-1)

.

Querying Submatrix Sum :

To get the sum of elements in the submatrix specified by corners
(row1, col1)

to
(row2, col2)

, we use the precomputed cumulative sums from
dp

.
The sum can be calculated as:

\text{sumRegion} = \text{dp}[row2+1][col2+1] - \text{dp}[row1][col2+1] - \text{dp}[row2+1][col1] + \text{dp}[row1][col1]

This formula subtracts the unnecessary outer regions and adds back the overlapping submatrix to get the correct sum.

Detailed Steps in Pseudocode

Initializing the NumMatrix class

                                            
class NumMatrix:
    # Initialization of NumMatrix with the given matrix
    function __init__(matrix):
        if matrix is empty:
            return  # Early exit if the matrix is empty
        
        num_rows = number of rows in matrix
        num_columns = number of columns in matrix
        
        # Initialize the dp table with an extra row and column with zeros
        dp = 2D array of size (num_rows + 1) x (num_columns + 1) filled with zeros
        
        # Fill the dp table with cumulative sums
        for i from 1 to num_rows:
            for j from 1 to num_columns:
                dp[i][j] = matrix[i-1][j-1] + dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1]

Summing the Region

                                            
    # Function to get the sum of the specified submatrix
    function sumRegion(row1, col1, row2, col2):
        # Compute the sum of the submatrix using the dp table
        return dp[row2+1][col2+1] - dp[row2+1][col1] - dp[row1][col2+1] + dp[row1][col1]

Explanation:

First, we add the sum of the submatrix ending at
(row2, col2)

which is
dp[row2+1][col2+1]

.
Then, we subtract the areas that extend beyond
(row1, col1)

by subtracting the sums ending at
(row2, col1-1)

and
(row1-1, col2)

.
Finally, we add back the area which extends beyond both boundaries twice, once for each, which is why we add back the sum ending at
(row1-1, col1-1)

.

By initializing our

dp

table during the object construction, we ensure that each query to sumRegion is handled in constant time, thus meeting the requirements of the challenge efficiently.