Tuesday, November 17, 2015

LeetCode OJ - Range Sum Query 2D - Immutable

Problem:

Solution:

Using the running sum formula in the last post, and also the inclusive exclusive principle, we get this

$\begin{eqnarray*} & & \sum\limits_{r = r_1}^{r_2} {\sum\limits_{c = c_1}^{c_2} {f(r, c)}} \\ &=& \sum\limits_{r = 0}^{r_2} {\sum\limits_{c = 0}^{c_2} {f(r, c)}} - \sum\limits_{r = 0}^{r_1-1} {\sum\limits_{c = 0}^{c_2} {f(r, c)}} - \sum\limits_{r = 0}^{r_2} {\sum\limits_{c = 0}^{c_1-1} {f(r, c)}} + \sum\limits_{i = 0}^{r_1-1-1} {\sum\limits_{j = 0}^{c_1-1} {f(r, c)}} \end{eqnarray*}$

Code:

#include "stdafx.h"

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

#include "LEET_RANGE_SUM_QUERY_2D_IMMUTABLE.h"
#include <map>
#include <iostream>
#include <sstream>
#include <vector>
#include <string>

using namespace std;

namespace _LEET_RANGE_SUM_QUERY_2D_IMMUTABLE
{
class NumMatrix
{
private:
vector<vector<int>> runningSums;
public:
NumMatrix(vector<vector<int>> &matrix)
{
int height = matrix.size();
if (height == 0)
{
return;
}

int width = matrix[0].size();
if (width == 0)
{
return;
}

// runningSum[i][j] = sum(r = 0 to i - 1) sum(c = 0 to j - 1) matrix[r][c]
runningSums.resize(height + 1);
for (int r = 0; r <= height; r++)
{
runningSums[r].resize(width + 1);
}

for (int i = 0; i <= height; i++)
{
for (int j = 0; j <= width; j++)
{
if (i == 0 || j == 0)
{
runningSums[i][j] = 0;
}
else
{
// Inclusive exclusive principle applies here
runningSums[i][j] = runningSums[i - 1][j] + runningSums[i][j - 1] - runningSums[i - 1][j - 1] + matrix[i - 1][j - 1];
}
}
}
}

int sumRegion(int row1, int col1, int row2, int col2)
{
// Inclusive exclusive principle applies here as well
return runningSums[row2 + 1][col2 + 1] - runningSums[row1][col2 + 1] - runningSums[row2 + 1][col1] + runningSums[row1][col1];
}
};
};

using namespace _LEET_RANGE_SUM_QUERY_2D_IMMUTABLE;

int LEET_RANGE_SUM_QUERY_2D_IMMUTABLE()
{
int row1[] = { 3, 0, 1, 4, 2 };
int row2[] = { 5, 6, 3, 2, 1 };
int row3[] = { 1, 2, 0, 1, 5 };
int row4[] = { 4, 1, 0, 1, 7 };
int row5[] = { 1, 0, 3, 0, 5 };
vector<vector<int>> nums;
nums.push_back(vector<int>(row1, row1 + _countof(row1)));
nums.push_back(vector<int>(row2, row2 + _countof(row2)));
nums.push_back(vector<int>(row3, row3 + _countof(row3)));
nums.push_back(vector<int>(row4, row4 + _countof(row4)));
nums.push_back(vector<int>(row5, row5 + _countof(row5)));
NumMatrix n(nums);
cout << (n.sumRegion(2, 1, 4, 3) == 8) << endl;
cout << (n.sumRegion(1, 1, 2, 2) == 11) << endl;
cout << (n.sumRegion(1, 2, 2, 4) == 12) << endl;
return 0;
}