300. Longest Increasing Subsequence

Difficulty: Medium

Frequency: N/A

 

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?


Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int lengthOfLIS(vector<int>& nums) {
        int n = nums.size();
        if (!n) return 0;
        int result = 0;
        vector<int> dp(n, 1);
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < i; j++) {
                if (nums[i] > nums[j]) dp[i] = max(dp[i], dp[j] + 1);
            }
            result = max(result, dp[i]);
        }
        return result;
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:


Submission errors:

 

Things to learn:

Advertisements

304. Range Sum Query 2D – Immutable

Difficulty: Medium

Frequency: N/A

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:

  1. You may assume that the matrix does not change.
  2. There are many calls to sumRegion function.
  3. You may assume that row1 ≤ row2 and col1 ≤ col2.

Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class NumMatrix {
private:
    vector<vector<int>> sums;
public:
    NumMatrix(vector<vector<int>> &matrix) {
        int m = matrix.size();
        int n = m > 0 ? matrix[0].size() : 0;
        sums = vector<vector<int>>(m + 1, vector<int>(n + 1, 0));
        for (int i = 1; i <= m; i++) {
            for (int j = 1; j <= n; j++) {
                sums[i][j] = matrix[i - 1][j - 1] + sums[i][j - 1] + sums[i - 1][j] - sums[i - 1][j - 1];
            }
        }
    }

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


// Your NumMatrix object will be instantiated and called as such:
// NumMatrix numMatrix(matrix);
// numMatrix.sumRegion(0, 1, 2, 3);
// numMatrix.sumRegion(1, 2, 3, 4);

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:


Submission errors:

 

Things to learn:

256. (Locked)Paint House

Difficulty: Medium

Frequency: N/A

 

There are a row of n houses, each house can be painted with one of the three colors: red, blue or green. The cost of painting each house with a certain color is different. You have to paint all the houses such that no two adjacent houses have the same color.

The cost of painting each house with a certain color is represented by a n x 3 cost matrix. For example, costs[0][0] is the cost of painting house 0 with color red;costs[1][2] is the cost of painting house 1 with color green, and so on… Find the minimum cost to paint all houses.

Note:
All costs are positive integers.


Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int minCost(vector<vector<int>>& costs) {
        if (costs.empty()) return 0;
        int n = costs.size(), r = 0, g = 0, b = 0;
        for (int i = 0; i < n; i++) {
            int pr = r, pg = g, pb = b;
            r = min(pg, pb) + costs[i][0];
            g = min(pr, pb) + costs[i][1];
            b = min(pr, pg) + costs[i][2];
        }
        return min(min(r, g), b);
    }
};


Submission errors:

 

Things to learn:

221. Maximal Square

Difficulty: Medium

Frequency: N/A

Given a 2D binary matrix filled with 0’s and 1’s, find the largest square containing all 1’s and return its area.

For example, given the following matrix:

1 0 1 0 0
1 0 1 1 1
1 1 1 1 1
1 0 0 1 0

Return 4.


Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int maximalSquare(vector<vector<char>>& matrix) {
        if (matrix.empty()) return 0;
        int m = matrix.size(), n = matrix[0].size();
        vector<vector<int>> size(m, vector<int>(n, 0));
        int maxSize = 0;
        for (int i = 0; i < m; i++) {
            if (matrix[i][0] == '1') {
                size[i][0] = 1;
                maxSize = max(maxSize, size[i][0]);
            }
        }
        for (int j = 1; j < n; j++) {
            if (matrix[0][j] == '1') {
                size[0][j] = 1;
                maxSize = max(maxSize, size[0][j]);
            }
        }
        for (int i = 1; i < m; i++) {
            for (int j = 1; j < n; j++) {
                if (matrix[i][j] == '1') {
                    size[i][j] = min(size[i - 1][j], min(size[i][j - 1], size[i - 1][j - 1])) + 1;
                    maxSize = max(maxSize, size[i][j]);
                }
            }
        }
        return maxSize * maxSize;
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:


Submission errors:

 

Things to learn:

213. House Robber II

Difficulty: Medium

Frequency: N/A

Note: This is an extension of House Robber.

After robbing those houses on that street, the thief has found himself a new place for his thievery so that he will not get too much attention. This time, all houses at this place are arranged in a circle. That means the first house is the neighbor of the last one. Meanwhile, the security system for these houses remain the same as for those in the previous street.

Given a list of non-negative integers representing the amount of money of each house, determine the maximum amount of money you can rob tonight without alerting the police.


Test Cases:


Solution 1:

Data structure:
Steps:
Complexity:
Runtime:
Space:
Code:
class Solution {
public:
    int rob(vector<int>& nums) {
        int n = nums.size();
        if (n == 0) return 0
        if (n == 1) return nums[0];
        int pre = 0, cur = 0;
        for (int i = 0; i < n - 1; i++) {
            int tmp = pre;
            pre = cur;
            cur = max(tmp + nums[i], pre);
        }
        int pre2 = 0, cur2 = 0;
        for (int i = 1; i < n; i++) {
            int tmp = pre2;
            pre2 = cur2;
            cur2 = max(tmp + nums[i], pre2);
        }
        return max(cur, cur2);
    }
};

Solution 2:

Data structure:
steps:
Complexity:
Runtime:
Space:
Code:


Submission errors:

 

Things to learn: