leetCode Question: Range Sum Query 2D - Immutable

Range Sum Query 2D - Immutable

Given a 2D matrix matrix, find the sum of the elements inside the rectangle defined by its upper left corner (row1, col1) and lower right corner (row2, col2).

Range Sum Query 2D
The above rectangle (with the red border) is defined by (row1, col1) = (2, 1) and (row2, col2) = (4, 3), which contains sum = 8.

Example:
Given matrix = [
[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]
]

sumRegion(2, 1, 4, 3) -> 8
sumRegion(1, 1, 2, 2) -> 11
sumRegion(1, 2, 2, 4) -> 12
Note:
You may assume that the matrix does not change.
There are many calls to sumRegion function.
You may assume that row1 ≤ row2 and col1 ≤ col2.

Analysis

First glance at this problem give us an intuitive but less efficient solution: Loop through row1 to row2, loop through col1 to col2, add the matrix element one by one.

Given the condition that there are many function calls, we could start thinking of more efficient algorithm. Since the matrix does not change, we could possiblly store some information before the "sumRegion" calls, in order to help on the time complexity.

Firstly let's simplify the problem to the following description:
given a matrix, and one point, which is the bottom right corner, compute the sum of the region between (0, 0) and the point.

It's more intuitive to draw the figure below ( see (1) ):

From the figure, we could see the procedure to compute the sum of region by addition and subtraction.

Looking back to the original problem, it is then not hard to find out (figure (2) ):

sumRegion(row1, col1, row2, col2) = sum( (row2, col2) ) - sum( (row1-1, col2) ) - sum( (row2, col1-1) ) + sum( (row1-1, col1-1) )

Now, the only thing of which you may not get the idea is the initialization part. Actually it is not that hard but need more attention dealing with the indices. Specifically, we build a matrix of the same size, where every position [ i, j ] stores the sum of element between [0 , 0] and [ i, j ]. We are still using the procedure shown in figure (1):

For each position [ i, j ] in our sum matrix, we are checking [ i-1, j ] and [ i, j-1 ], the sum of [ i, j ] is:
m[ i, j ] = m[ i-1, j ] + m[ i, j-1 ] - m[ i-1, j-1 ], the procedure is shown below:

Code (C++)

class NumMatrix {

public:

NumMatrix(vector<vector<int>> matrix) {

nrow = matrix.size();

if (nrow == 0){ return; }

ncol = matrix[0].size();

matrix_sum = vector<vector<int>> (nrow+1, vector<int>(ncol+1, 0));

for (int i=1;i <= nrow; ++i){

for (int j=1;j <= ncol; ++j){

matrix_sum[i][j] = matrix_sum[i-1][j] + matrix_sum[i][j-1] - matrix_sum[i-1][j-1] + matrix[i-1][j-1];

}

}

}

int sumRegion(int row1, int col1, int row2, int col2) {

int p1_i, p1_j, p2_i, p2_j, p3_i, p3_j, p4_i, p4_j;

p1_i = row1;

p1_j = col1;

p2_i = row1;

p2_j = col2 + 1;

p3_i = row2+1;

p3_j = col2+1;

p4_i = row2+1;

p4_j = col1;

return matrix_sum[p3_i][p3_j] - matrix_sum[p2_i][p2_j] - matrix_sum[p4_i][p4_j] + matrix_sum[p1_i][p1_j];

}

private:

vector<vector<int> > matrix_sum;

int nrow;

int ncol;

};

/**

* Your NumMatrix object will be instantiated and called as such:

* NumMatrix obj = new NumMatrix(matrix);

* int param_1 = obj.sumRegion(row1,col1,row2,col2);

*/

Code (Python)

class NumMatrix(object):

def __init__(self, matrix):

"""

:type matrix: List[List[int]]

"""

if len(matrix) == 0:

return

self.n_row = len(matrix)

self.n_col = len(matrix[0])

self.matrix_sum = [ [0 for i in range(self.n_col+1)] for j in range(self.n_row+1)]

for i in xrange(1, self.n_row+1):

for j in xrange(1, self.n_col+1):

self.matrix_sum[i][j] = self.matrix_sum[i-1][j] + self.matrix_sum[i][j-1] - self.matrix_sum[i-1][j-1] + matrix[i-1][j-1]

def sumRegion(self, row1, col1, row2, col2):

"""

:type row1: int

:type col1: int

:type row2: int

:type col2: int

:rtype: int

"""

p1_i, p1_j = row1, col1

p2_i, p2_j = row1, col2 + 1

p3_i, p3_j = row2 + 1, col2 + 1

p4_i, p4_j = row2 + 1, col1

return self.matrix_sum[p3_i][p3_j] + self.matrix_sum[p1_i][p1_j] - self.matrix_sum[p2_i][p2_j] - self.matrix_sum[p4_i][p4_j]

# Your NumMatrix object will be instantiated and called as such:

# obj = NumMatrix(matrix)

# param_1 = obj.sumRegion(row1,col1,row2,col2)

leetCode Question: Longest Increasing Subsequence

Longest Increasing Subsequence

Given an unsorted array of integers, find the length of longest increasing subsequence.

For example,
Given [10, 9, 2, 5, 3, 7, 101, 18],
The longest increasing subsequence is [2, 3, 7, 101], therefore the length is 4. Note that there may be more than one LIS combination, it is only necessary for you to return the length.

Your algorithm should run in O(n2) complexity.

Follow up: Could you improve it to O(n log n) time complexity?

Analysis:

The simple but relatively slow solution is classic DP (dynamic programming) approach. For now, I will analyze this solution in detail and breifly introduce the n log n algorithm.

For each index i in the array nums, we could have an array res to store the length of longest increasing subsequence from nums[ 0 ] to nums[ i ]. For index i, we have multiple numbers from nums[ 0 ] to nums[ i-1 ], also, we have multiple results from res[ 0 ] to res[ i ]. Denote j is index from 0 to i-1, for each possible j, if nums[ i ] > nums[ j ] (current number > one previous number), it means the longest increasing subsequence that ends at num[ j ] + num[ i ] is a valid increasing subsequence, and the length of it is res[ j ] + 1. So if we got the longest length of all possible j (from 0 to i-1), it should be the longest length in current index i. The outer loop for i is just the scan the whole nums array from the begining to the end. In the end, the maximum value in array res, is the final longest length we want.

In the figure above, blue color means the data array (green font mean the actural longest increading subseuqnce), red color means the result array storing the longest length.

In the above solution, everytime we have to look back and check from 0 to current index - 1 for updating the current index. This look back part is most time consuming. So for the n log( n ) algorithm, we have to modify the look back part. Instead of looking back, we could have a new array s, s[ i ] stores the minimum A[i] when the len of longest increaing seq is d[ i ]. It is not hard to observe array s is ordered. Then, for each nums [ i ], we search the array s[ i ], to find the index j where s[ j ] is less than but closest to nums[ i ]. The index j is then the result.

Code (C++) (Simple DP):

class Solution {

public:

int lengthOfLIS(vector<int>& nums) {

if (nums.size()==0){return 0;}

int res_max = 1;

vector<int> res(nums.size(), 1);

for (int i=1;i< nums.size();i++){

for (int j = 0; j < i; j++){

if (nums[i] > nums[j]){

res[i] = max(res[i], res[j] + 1);

}

}

//cout << res[i] << ", ";

res_max = max(l, res[i]);

}

return res_max;

}

};

Code (Python) (Simple DP):

class Solution(object):

def lengthOfLIS(self, nums):

"""

:type nums: List[int]

:rtype: int

"""

if len(nums) == 0:

return 0

res_max = 1

res = [1]*len(nums)

for i in range(len(nums)):

for j in range(0,i):

if nums[i] > nums[j]:

res[i] = max(res[j]+1, res[i])

res_max = max(res_max, res[i])

return res_max

leetcode Question: Range Sum Query - Immutable

Range Sum Query - Immutable

Given an integer array nums, find the sum of the elements between indices i and j (i ≤ j), inclusive.

Example:
Given nums = [-2, 0, 3, -5, 2, -1]

sumRange(0, 2) -> 1
sumRange(2, 5) -> -1
sumRange(0, 5) -> -3
Note:
You may assume that the array does not change.
There are many calls to sumRange function.

Analysis:

This is a simple DP problem. By just watching the example, we could easily find the solution:

nums = [-2, 0, 3, -5, 2, -1]

For each index i we could compute the sum from 0 to i:

sum = [-2, -2+0, -2+0+3, -2+0+3-5, -2+0+3-5+2, -2+0+3-5+2-1]

Therefore, if we want to find the sum between i and j:

• sum[ i ] can be viewed as sum[ 0 to i ]
• sum[ j ] can be viewed as sum[ 0 to j ]
• sum[ i-1 ] + sum[ i to j ] = s[ 0 to j ]
• sum [ i to j ] = sum[ j ] - sum[ i-1 ]

Code (C++):

class NumArray {

public:

NumArray(vector<int> &nums) {

sums = nums;

for (int i = 1; i< nums.size(); i++){

sums[i] = sums[i-1] + nums[i];

}

}

int sumRange(int i, int j) {

return i==0 ? sums[j] : sums[j] - sums[i-1];

}

private:

vector<int> sums;

};

// Your NumArray object will be instantiated and called as such:

// NumArray numArray(nums);

// numArray.sumRange(0, 1);

// numArray.sumRange(1, 2);

Code (Python):

class NumArray(object):

def __init__(self, nums):

"""

initialize your data structure here.

:type nums: List[int]

"""

self.sums = nums[:]

for i in range(1, len(self.sums)):

self.sums[i] = self.sums[i-1] + nums[i]

def sumRange(self, i, j):

"""

sum of elements nums[i..j], inclusive.

:type i: int

:type j: int

:rtype: int

"""

if i == 0:

return self.sums[j]

else:

return self.sums[j] - self.sums[i-1]

# Your NumArray object will be instantiated and called as such:

# numArray = NumArray(nums)

# numArray.sumRange(0, 1)

# numArray.sumRange(1, 2)

leetcode Question: Perfect Squares

Perfect Squares

Given a positive integer n, find the least number of perfect square numbers (for example, 1, 4, 9, 16, ...) which sum to n.

For example, given n = 12, return 3 because 12 = 4 + 4 + 4; given n = 13, return 2 because 13 = 4 + 9.

Analysis:

For this problem, I'd like to show the approach using BFS, and the DP. These methods is not very optimal since there is a mathematical soluiton can runs much faster. However, this problem also serves as a good practice for the BFS and DP.

The BFS approach considers finding the min numbers as a search problem. Specifically, the root node is the positive integer n, every time we subtract the value n with all the posiblle square values, which can be considered as a path from parent node to the child node. The goal is to find the shortest path, connect from root node to the node in which the value is zero. A simple way to reduce the computations is that: we could eliminate the node which we have seen before, since the path go through (if exists) the newly seen node, must not as short as any path that go through the previously seen node with same value.

The DP solution goes pretty straightforward, since for every value n, it must come from some value plus a square number. This can be written as:
d[n] = min(d[n - i * i] + 1), where d[n] is the least number of square numbers, and i * i <= n.

Code (C++) (BFS version):

class Solution {

public:

int numSquares(int n) {

queue<pair<int,int>> q;

map<int,bool> mp;

q.push(make_pair(n,1));

int val = 0;

int dep = 0;

while (!q.empty()){

val = q.front().first;

dep = q.front().second;

q.pop();

int i=1;

while (i*i <= val){i++;}

while (i>=1){

if (val-i*i == 0){

return dep;

}

if (mp.find(val-i*i)==mp.end()){

q.push(make_pair(val-i*i,dep+1));

mp[val-i*i] = true;

}

i--;

}

}

return dep;

}

};

Code (C++, DP version):

class Solution {

public:

int numSquares(int n) {

vector<int> res(n+1, INT_MAX);

res[0] = 0;

for (int i=0;i<=n; i++){

for (int j=1; j*j <= i; j++){

res[i] = min(res[i-j*j]+1, res[i]);

}

}

return res[n];

}

};

Code (Python, DP version):

class Solution(object):

def numSquares(self, n):

"""

:type n: int

:rtype: int

"""

res = [sys.maxint]*(n+1)

res[0] = 0

for i in range(1,n+1):

j = 1

while j*j <=i:

res[i] = min(res[i-j*j]+1, res[i])

j+=1

return res[n]