[leetcode #304] Range Sum Query 2D - Immutable

Problem

Given a 2D matrix matrix, handle multiple queries of the following type:

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

NumMatrix(int[][] matrix) Initializes the object with the integer matrix matrix.
int sumRegion(int row1, int col1, int row2, int col2) Returns the sum of the elements of matrix inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Example 1:

Input

["NumMatrix", "sumRegion", "sumRegion", "sumRegion"]
[[[[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]]], [2, 1, 4, 3], [1, 1, 2, 2], [1, 2, 2, 4]]

Output

[null, 8, 11, 12]

Explanation

NumMatrix numMatrix = new NumMatrix([[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]]);
numMatrix.sumRegion(2, 1, 4, 3); // return 8 (i.e sum of the red rectangle)
numMatrix.sumRegion(1, 1, 2, 2); // return 11 (i.e sum of the green rectangle)
numMatrix.sumRegion(1, 2, 2, 4); // return 12 (i.e sum of the blue rectangle)

Constraints:

· m == matrix.length
· n == matrix[i].length
· 1 <= m, n <= 200
· -10⁵ <= matrix[i][j] <= 10⁵
· 0 <= row1 <= row2 < m
· 0 <= col1 <= col2 < n
· At most 10⁴ calls will be made to sumRegion.

Idea

두 점이 input으로 주어지면 두 점으로 만드는 사각형 내 숫자들의 합이 얼만지 구하는 문제다.

NumMatrix를 초기화할 때 running sum을 미리 계산해 새로운 matrix에 저장한다.

두 점이 주어지면 running sum을 이용해 사각형 내의 합을 O(1)로 구할 수 있다.

Time Complexity: O(1)
Space Complexity: O(1) - matrix의 크기

Solution

class NumMatrix {
    int rowLen;
    int colLen;
    int[][] runningSum;

    public NumMatrix(int[][] matrix) {
        rowLen = matrix.length;
        colLen = matrix[0].length;
        runningSum = new int[rowLen][colLen];
        setRunningSum(matrix);
    }

    private void setRunningSum(int[][] matrix) {
        int sum = 0;
        for (int i=0; i < rowLen; i++) {
            for (int j=0; j < colLen; j++) {
                if (i == 0 && j == 0) {
                    runningSum[i][j] = matrix[i][j];
                } else if (i == 0 && j != 0) {
                    runningSum[i][j] = runningSum[i][j-1] + matrix[i][j];
                } else if (i != 0 && j == 0) {
                    runningSum[i][j] = runningSum[i-1][j] + matrix[i][j];
                } else {
                    runningSum[i][j] = runningSum[i-1][j] + runningSum[i][j-1] - runningSum[i-1][j-1] + matrix[i][j];
                }
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        int res = runningSum[row2][col2];

        if (row1 > 0) {
            res -= runningSum[row1-1][col2];
        }

        if (col1 > 0) {
            res -= runningSum[row2][col1-1];
        }

        if (row1 > 0 && col1 > 0) {
            res += runningSum[row1-1][col1-1];
        }

        return res;
    }
}

/**
 * Your NumMatrix object will be instantiated and called as such:
 * NumMatrix obj = new NumMatrix(matrix);
 * int param_1 = obj.sumRegion(row1,col1,row2,col2);
 */

Reference

https://leetcode.com/problems/range-sum-query-2d-immutable/