Range Sum Query Immutable

Problem

Analysis

  • We need to set the lower and upper bounds as per given indices.
    Example:

    1
    2
    3
    4
    5
    for given example
    sumRegion(2, 1, 4, 3)

    we iterate row from 2 to 4 inclusive
    we iterate col from 1 to 3 inclusive

  • matrix is immutable

First Attempt

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
class NumMatrix {
    int r1, r2;
    int c1, c2;
    int rsize, csize;
    vector<vector<int>> m;
public:
    NumMatrix(vector<vector<int>> matrix) {
        rsize = matrix.size();
        csize = matrix[0].size();
        for (auto e: matrix) {
            m.push_back(e);
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
        if !((0 <= row1 < rsize) &&
             (0 <= row2 < rsize) &&
             (0 <= col1 < csize) &&
             (0 <= col2 < csize)
            )
            return 0;
        int sum = 0;
        for (int r = row1; r <= row2; r++) {
            for (int c = col1; c <= col2; c++) {
                sum += m[r][c];
            }
        }


    }
};

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

Amended Solution

While the solution above is in the right spirit. The execution suffers.

  1. The expressions of the form (0 <= row1 < rsize) are erroneous.
  2. We should check for the case of empty matrix
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
class NumMatrix {
    int r1 = 0, r2 = 0;
    int c1 = 0, c2 = 0;
    int rsize = 0, csize = 0;
    vector<vector<int>> m;
public:
    NumMatrix(vector<vector<int>> matrix) {
        if (!matrix.empty()) {
            rsize = matrix.size();
            csize = matrix[0].size();
            for (auto e: matrix) {
                m.push_back(e);
            }
        }
    }

    int sumRegion(int row1, int col1, int row2, int col2) {
            if (row1 < 0 || row1 > rsize ||
               row2 < 0 || row2 > rsize ||
               col1 < 0 || col1 > csize ||
               col2 < 0 || col2 > csize)
            {
             return -1;
            }
        int sum = 0;
        for (int r = row1; r <= row2; r++) {
            for (int c = col1; c <= col2; c++) {
                sum += m[r][c];
            }
        }

        return sum;
    }
};

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