Paint House I -- DP -- Leetcode

Question:

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.

Answer:
Time: O(n * 3) = O(n), Space: O(1)
public int minCost(int[][] costs) {
        if(costs==null)return 0;
        int m = costs.length;
        if(m==0)return 0;
     
        for(int i=1;i<m;++i){
            costs[i][0] += Math.min(costs[i-1][1], costs[i-1][2]);
            costs[i][1] += Math.min(costs[i-1][0], costs[i-1][2]);
            costs[i][2] += Math.min(costs[i-1][0], costs[i-1][1]);
        }
        int res = Math.min(costs[m-1][0], Math.min(costs[m-1][1], costs[m-1][2]));
        return res;
    }

Paint House II -- DP -- Leetcode

Question:

There are a row of n houses, each house can be painted with one of the k colors. 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 k cost matrix. For example, costs[0][0] is the cost of painting house 0 with color 0; costs[1][2] is the cost of painting house 1 with color 2, and so on... Find the minimum cost to paint all houses.

Note:
All costs are positive integers.

Follow up:
Could you solve it in O(nk) runtime?

Answer:

1. Basic: Time: O(n * k * k), Space: O(1)

public int minCostII(int[][] costs) {

        if(costs==null)return 0;

        int n = costs.length;

        if(n==0)return 0;

        if(costs[0]==null)return 0;

        int k = costs[0].length;

        if(k==0)return 0;

        

        //Time: O(n*k*k)

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

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

                 int min = Integer.MAX_VALUE;

                 for(int w=0;w<k;++w){

                    if(w!=j){

                        min = Math.min(costs[i-1][w], min);

                    }

                 }

                 costs[i][j] += min;

            }

        int res = Integer.MAX_VALUE;

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

            res = Math.min(res, costs[n-1][j]);

        }

        return res;

}

2. Followup: Time: O(n * k), Space: O(1)

public int minCostII(int[][] costs) {

        if(costs==null)return 0;

        int n = costs.length;

        if(n==0)return 0;

        if(costs[0]==null)return 0;

        int k = costs[0].length;

        if(k==0)return 0;

        

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

            //Time: O(n * k)

            int min1 = Integer.MAX_VALUE;

            int min2 = min1;

            int minIndex1 = -1;

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

                if(costs[i-1][j] < min1){

                    min2 = min1;

                    min1 = costs[i-1][j];

                    minIndex1 = j;

                }else if(costs[i-1][j] >= min1 && costs[i-1][j] < min2){

                    min2 = costs[i-1][j];

                }

            }

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

               if(j == minIndex1){

                   costs[i][j] += min2;

               }else{

                   costs[i][j] += min1;

               }

            }

        }

        

        int res = Integer.MAX_VALUE;

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

            res = Math.min(res, costs[n-1][j]);

        }

        return res;

}

Maximal Rectangle -- Leetcode -- FB

Question:

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

Answer:

 /* Example: output: 6!

    0,0,0,1,0

    0,1,1,1,0

    1,0,1,1,0

    0,0,1,1,0

    0,0,0,0,1

    */

public class Solution {

    public int maximalRectangle(char[][] matrix) {

        if(matrix==null)return 0;

        int m = matrix.length;

        if(m==0)return 0;

        if(matrix[0]==null)return 0;

        int n = matrix[0].length;

        

        int maxRecArea = 0;

        int[] dp = new int[n];

        

        //Time: O(m * n)

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

            //Time: O(n)

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

                if(matrix[i][j] == '1'){

                    dp[j] += 1;

                }else{

                    dp[j] = 0;

                }

            }

            //Time: O(2 * n), Space: O(n)

            int area = largestRectangleArea(dp);

            maxRecArea = Math.max(maxRecArea, area);

        }

        return maxRecArea;

    }

//Time: O(n), Space: O(n)

    public int largestRectangleArea(int[] heights) {

        Stack<Integer> stack = new Stack<Integer>();

        int maxArea = 0;

        

        int[] h = new int[heights.length + 1];

        h = Arrays.copyOf(heights, heights.length + 1);

        

        int i=0;

        while(i < h.length){

            if(stack.isEmpty() || h[i] >= h[stack.peek()]){

                stack.push(i++);

            }else{

                //!stack.isEmpty() && h[i] < h[stack.peek()]

                int t = stack.pop();

                int area = 0;

                if(stack.isEmpty()){

                    area = h[t] * i;

                }else{

                    area = h[t] * (i - stack.peek() - 1);

                }

                maxArea = Math.max(maxArea, area);

            }

        }

        return maxArea;

    }

}

H-Index -- Leetcode

Question:

Given an array of citations (each citation is a non-negative integer) of a researcher, write a function to compute the researcher's h-index.

According to the definition of h-index on Wikipedia: "A scientist has index h if h of his/her N papers have at least h citations each, and the other N − h papers have no more than h citations each."

For example, given citations = [3, 0, 6, 1, 5], which means the researcher has 5 papers in total and each of them had received 3, 0, 6, 1, 5 citations respectively. Since the researcher has 3 papers with at least 3 citations each and the remaining two with no more than 3 citations each, his h-index is 3.

Note: If there are several possible values for h, the maximum one is taken as the h-index.

Hint:

1. An easy approach is to sort the array first.
2. What are the possible values of h-index?
3. A faster approach is to use extra space.

Answer:

Time: O(n), Space:O(n), Using bucket sort or hashmap, faster than sort method! 

public int hIndex(int[] citations) {
        int len = citations.length;
        HashMap<Integer, Integer> hmap = new HashMap<Integer, Integer>();
        for(int i=0; i<len; ++i){
            int val = citations[i];
            if(val >= 1 && val <= len){
                if(!hmap.containsKey(val)){
                    hmap.put(val, 1);
                }else{
                    hmap.put(val, hmap.get(val) + 1);
                }
            }else if(val > len){
                if(!hmap.containsKey(len)){
                    hmap.put(len, 1);
                }else{
                    hmap.put(len, hmap.get(len) + 1);
                }
            }
        }
        int count = 0;
        for(int i=len; i>=1; --i){
            if(hmap.containsKey(i)){
                count += hmap.get(i);
            }
            if(count >= i){
                return i;
            }
        }
        return 0;
    }

H-Index II -- Leetcode

Question:

Follow up for H-Index: What if the citations array is sorted in ascending order? Could you optimize your algorithm?

Hint:

1. Expected runtime complexity is in O(log n) and the input is sorted.

Answer:

Keyword: Binary Search, O(log n).

    //0,3,7,8,9

    public int hIndex(int[] citations) {

        int len = citations.length;

        int start = 0;

        int end = len - 1;

        while(start <= end){

            int mid = start + (end - start) / 2;

            

            int index = len - mid;

            if(citations[mid] >= index && (mid == 0 || citations[mid-1] <= index) ){

                return index;

            }else if(citations[mid] < index){

                start = mid + 1;

            }else{

                end = mid - 1;

            }

        }

        return 0;

    }

Increasing Triplet Subsequence -- Leetcode -- FB

Question:

Given an unsorted array return whether an increasing subsequence of length 3 exists or not in the array.

Formally the function should:

Return true if there exists i, j, k 
such that arr[i] < arr[j] < arr[k] given 0 ≤ i < j < k ≤ n-1 else return false.

Your algorithm should run in O(n) time complexity and O(1) space complexity.

Examples:
Given [1, 2, 3, 4, 5],
return true.

Given [5, 4, 3, 2, 1],
return false.

Answer:
Time: O(n), Space: O(1)
public boolean increasingTriplet(int[] nums) {
        if(nums==null || nums.length==0)return false;
        int max = Integer.MAX_VALUE;
        int min = nums[0];
     
        for(int i=1; i<nums.length; ++i){
            if(nums[i] < min){
                min = nums[i];
            }else if(nums[i] > max){
                return true;
            }else if(nums[i] > min && nums[i] < max){
                max = nums[i];
            }
        }
        return false;
    }

Add Binary String -- Java -- Leetcode -- FB

Question:

Given two binary strings, return their sum (also a binary string).

For example,
a = "11"
b = "1"
Return "100".

Answer:

//Traverse from tail to head:

public class Solution {

    public String addBinary(String a, String b) {

        int len1 = a.length();

        int len2 = b.length();

        if(a==null || len1==0)return b;

        if(b==null || len2==0)return a;

        

        int pa = len1-1;

        int pb = len2-1;

        int flag = 0;

        StringBuilder sb = new StringBuilder();

        

        while(pa >= 0 || pb >= 0){

            //reset every time!

            int va = 0;

            int vb = 0;

            

            if(pa >= 0){

               va = Integer.parseInt("" + a.charAt(pa));

               pa--;

            }

            if(pb >= 0){

                vb = Integer.parseInt("" + b.charAt(pb));

                pb--;

            }

            int sum = va + vb + flag;

            if(sum >= 2){

                flag = 1;

                sb.insert(0, sum-2);

            }else{

                flag = 0;

                sb.insert(0, sum);

            }

        }

        if(flag==1){

            sb.insert(0, 1);

        }

        return sb.toString();

    }

}

Edit Distance -- DP -- Leetcode

Question:

Given two words word1 and word2, find the minimum number of steps required to convert word1 to word2. (each operation is counted as 1 step.)

You have the following 3 operations permitted on a word:

a) Insert a character
b) Delete a character
c) Replace a character

Answer:
DP!
public int minDistance(String word1, String word2) {
        int len1 = word1.length();
        int len2 = word2.length();
        if(len1==0)return len2;
        if(len2==0)return len1;
     
        int[][] dp = new int[len1+1][len2+1];
     
        for(int i=0;i<=len1;++i){
            dp[i][0] = i;
        }
        for(int i=1;i<=len2;++i){
            dp[0][i] = i;
        }
     
        for(int i=0;i<len1;++i){
            for(int j=0;j<len2;++j){
                // DP formular!
                if(word1.charAt(i) == word2.charAt(j)){
                    dp[i+1][j+1] = dp[i][j];
                }else{
                    dp[i+1][j+1] = minInThree(dp[i][j+1],  dp[i+1][j],  dp[i][j]) + 1;
                }
            }
        }
        return dp[len1][len2];
    }
 
    public int minInThree(int a, int b, int c){
        return Math.min(c, Math.min(a,b));
    }

Subsets II -- Leetcode

Question:

Given a collection of integers that might contain duplicates, nums, return all possible subsets.

Note:

• Elements in a subset must be in non-descending order.
• The solution set must not contain duplicate subsets.

For example,
If nums = [1,2,2], a solution is:

[
  [2],
  [1],
  [1,2,2],
  [2,2],
  [1,2],
  []
]

Answer:
public class Solution {
    public List<List<Integer>> subsetsWithDup(int[] nums) {
        List<Integer> subres = new ArrayList<Integer>();
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        int len = nums.length;
        if(len==0)return res;
       
        Arrays.sort(nums);
        DFS(res, subres, 0, nums);
        return res;
    }
   
    public void DFS(List<List<Integer>> res, List<Integer> subres, int index, int[] nums){
        List<Integer> newsubres = new ArrayList<Integer>(subres);
        res.add(newsubres);
        if(index >= nums.length){
            return;
        }
       
        for(int i=index; i<nums.length; ++i){
            //Avoid duplicate set!
            if(i!=index && nums[i]==nums[i-1]){
                continue;
            }
            subres.add(nums[i]);
            DFS(res, subres, i+1, nums);
            subres.remove(subres.size()-1);
        }
        return;
    }
}

Range Sum Query - Immutable -- Leetcode

Question:

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).

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.

Answer:

public class NumMatrix {
    int[][] dp;
    int m;
    int n;
   
    public NumMatrix(int[][] matrix) {
        m = matrix.length;
        if(m==0)return;
        n = matrix[0].length;
        if(m == 0 || n==0)return;
        dp = new int[m+1][n+1];
       
        for(int i=1; i<=m; ++i){
            for(int j=1; j<=n; ++j){
               dp[i][j] = dp[i-1][j] + dp[i][j-1] - dp[i-1][j-1] + matrix[i-1][j-1];    
            }
        }
    }

    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(row1<0 || col1<0)return -1;
        return dp[row2+1][col2+1] - dp[row2+1][col1] - dp[row1][col2+1] + dp[row1][col1];
    }
}


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

Range Sum Query 2D - Mutable -- Leetcode

Question:

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).

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
update(3, 2, 2)
sumRegion(2, 1, 4, 3) -> 10

Note:

1. The matrix is only modifiable by the update function.
2. You may assume the number of calls to update and sumRegion function is distributed evenly.
3. You may assume that row1 ≤ row2 and col1 ≤ col2.

Answer: 

Binary indexed tree solution: Time:  O(log m * log n), Space: O(m * n)

public class NumMatrix {
    //Space: O(m * n)
    int[][] tree, arr;
    int m;
    int n;
   
    public NumMatrix(int[][] matrix) {
        m = matrix.length;
        if(m==0)return;
        n = matrix[0].length;
        if(m == 0 || n==0)return;
        tree = new int[m+1][n+1];
        arr = new int[m][n];
       
        for(int i=0; i<m; ++i){
            for(int j=0; j<n; ++j){
               update(i, j, matrix[i][j]);    
            }
        }
    }

    //Time: O(logm * logn)
    public void update(int row, int col, int val) {
        int dif = val - arr[row][col];
        //update new value in element array!
        arr[row][col] = val;
        //update dif in BIT accumulated sume array!
        for(int i = row + 1; i <= m; i += i & (-i)){
            for(int j = col + 1; j <=n; j += j & (-j)){
                tree[i][j] += dif;
            }
        }
        return;
    }

    //Time: 4 * O(logm * logn) = O(logm * logn)
    public int sumRegion(int row1, int col1, int row2, int col2) {
        if(row1<0 || col1<0)return -1;
        return getSum(row2, col2) - getSum(row2, col1-1) - getSum(row1-1, col2) + getSum(row1-1, col1-1);
    }
   
    public int getSum(int row, int col){
        int sum = 0;
        for(int i = row + 1; i > 0; i -= i & (-i)){
            for(int j = col + 1; j > 0; j -= j & (-j)){
                sum += tree[i][j];
            }
        }
        return sum;
    }
}


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

Count of smaller numbers after self -- Leetcode

Question:

You are given an integer array nums and you have to return a new counts array. The counts array has the property where counts[i] is the number of smaller elements to the right of nums[i].

Example:

Given nums = [5, 2, 6, 1]

To the right of 5 there are 2 smaller elements (2 and 1).
To the right of 2 there is only 1 smaller element (1).
To the right of 6 there is 1 smaller element (1).
To the right of 1 there is 0 smaller element.

Return the array [2, 1, 1, 0].

Answer:
Using Binary Indexed Tree(BIT), time: O(N * log N), space: O(1 -- range) array.  Better than naive solution O(N*N). 

public class Solution {
    public List<Integer> countSmaller(int[] nums) {
        List<Integer> res = new ArrayList<Integer>();
       
        Integer min = Integer.MAX_VALUE;
        Integer max = Integer.MIN_VALUE;
        for(int i=0;i<nums.length;++i){
            min = Math.min(min, nums[i]);
            max = Math.max(max, nums[i]);
        }
        int range = max - min + 1;
        int[] tree = new int[range+1];

        for(int i = nums.length - 1; i >= 0; --i){
            int count = getCount(nums[i]-min, tree);
            res.add(0, count);
            addToCount(nums[i]-min+1, tree);
        }
        return res;
    }
   
    public int getCount(int i, int[] tree){
        int count = 0;
        while(i >= 1){
            count += tree[i];
            i -= i & (-i);
        }
        return count;
    }
   
    public void addToCount(int i, int[] tree){
        while(i <= tree.length-1){
            tree[i]++;
            i += i & (-i);
        }
    }
}

First Bad Version -- Leetcode

Question:

You are a product manager and currently leading a team to develop a new product. Unfortunately, the latest version of your product fails the quality check. Since each version is developed based on the previous version, all the versions after a bad version are also bad.

Suppose you have n versions [1, 2, ..., n] and you want to find out the first bad one, which causes all the following ones to be bad.

You are given an API bool isBadVersion(version) which will return whether version is bad. Implement a function to find the first bad version. You should minimize the number of calls to the API.

Answer:

Binary Search, Time: O(log n), Space:O(1)

/* The isBadVersion API is defined in the parent class VersionControl.

      boolean isBadVersion(int version); */

public class Solution extends VersionControl {

    

    public int firstBadVersion(int n) {

        int start = 1, end = n;

        

        while(start + 1 < end){

            int mid = start + (end - start) / 2;

            if(isBadVersion(mid)){

                end = mid;

            }else{

                start = mid;

            }

        }

        if(isBadVersion(start)){

            return start;

        }

        if(isBadVersion(end)){

            return end;

        }

        return -1;

    }

}

Pascal's Triangle -- Leetcode

Question:

Given numRows, generate the first numRows of Pascal's triangle.

For example, given numRows = 5,
Return

[
     [1],
    [1,1],
   [1,2,1],
  [1,3,3,1],
 [1,4,6,4,1]
]

Answer:

public class Solution {

    public List<List<Integer>> generate(int numRows) {
        List<List<Integer>> res = new ArrayList<List<Integer>>();
        if(numRows <= 0) return res;
       
        List<Integer> subres = new ArrayList<Integer>();
        subres.add(1);
        res.add(new ArrayList<Integer>(subres));
       
        for(int i = 1; i < numRows; ++i){
            for(int j = i-2; j >= 0; --j){
                subres.set(j+1, subres.get(j) + subres.get(j+1));
            }
            subres.add(1);
            res.add(new ArrayList<Integer>(subres));
        }
       
        return res;
    }
}

Pascal's Triangle II -- Leetcode

Question:

Given an index k, return the kth row of the Pascal's triangle.

For example, given k = 3,
Return [1,3,3,1].

Note:
Could you optimize your algorithm to use only O(k) extra space?

Answer:
public class Solution {

    public List<Integer> getRow(int rowIndex) {
        List<Integer> res = new ArrayList<Integer>();
        if（rowIndex <= 0) return res;

        res.add(1);

        for(int i = 1; i <= rowIndex; ++i){
            for(int j = i-2; j >= 0; --j){
                res.set(j+1, res.get(j) + res.get(j+1));
            }
            res.add(1);
        }
        return res;
    }
}

Anagram -- Leetcode

1. Valid Anagram:

Question:
https://leetcode.com/problems/valid-anagram/

Solution:

    public boolean isAnagram(String s, String t) {
        if(s.length() != t.length()){
            return false;
        }
       
        int[] charArr = new int[26];
        char[] chars = s.toCharArray();
        char[] chart = t.toCharArray();
        for(int i=0; i<s.length(); ++i){
            charArr[chars[i]-'a']++;
        }
        for(int i=0; i<t.length(); ++i){
            if(--charArr[chart[i]-'a'] < 0){
                return false;
            }
        }
        return true;
    }


2. Group Anagram

Question:
https://leetcode.com/problems/anagrams/

Solution:
Method 1:
key = String (sorted)
value = List<String>
Group : HashMap< String, List<String> >

Time: O(n * mlog m)

    public List<List<String>> groupAnagrams(String[] strs) {
        List<String> subres = new ArrayList<String>();
        List<List<String>> res = new ArrayList<List<String>>();
        Map<String, List<String>> hmap = new HashMap<String, List<String>>();
       
        //Time : n * logn
        Arrays.sort(strs);
        //Time : n * mlogm, Space : hmap : O(n)
        for(String s : strs){
            //sort s to get key, nlogn
            char[] charArr = s.toCharArray();
            Arrays.sort(charArr);
            String sortedStr = String.valueOf(charArr);
           
            if(!hmap.containsKey(sortedStr)){
                hmap.put(sortedStr, new ArrayList<String>());
            }
            hmap.get(sortedStr).add(s);
        }
       
        res.addAll(hmap.values());
        return res;
    }



Method 2:
key = HashMap<Character, Integer>
value = List<String>
Group : HashMap< HashMap<Character, Integer>, List<String> >

Time: O(n * (m + 26))

public List<List<String>> groupAnagrams(String[] strs) {
        List<String> subres = new ArrayList<String>();
        List<List<String>> res = new ArrayList<List<String>>();
        Map<String, List<String>> hmap = new HashMap<String, List<String>>();
       
        Arrays.sort(strs);
        //O(n)
        for(String s : strs){
            int[] charArr = new int[26];
            char[] chars = s.toCharArray();
            //Time : O(m + 26), Space : O(26) + O(n)
            for(int i=0; i<s.length(); ++i){
                charArr[chars[i]-'a']++;
            }
            StringBuilder sb = new StringBuilder();
            for(int i=0;i<26;++i){
               sb.append("" + i + charArr[i]);
            }
            String setStr = sb.toString();
           
            if(!hmap.containsKey(setStr)){
                hmap.put(setStr, new ArrayList<String>());
            }
            hmap.get(setStr).add(s);
        }
       
        res.addAll(hmap.values());
        return res;
    }