Super Ugly Number

Write a program to find the nth super ugly number.

Super ugly numbers are positive numbers whose all prime factors are in the given prime list primes of size k. For example, [1, 2, 4, 7, 8, 13, 14, 16, 19, 26, 28, 32]is the sequence of the first 12 super ugly numbers given primes = [2, 7, 13, 19] of size 4.

Note:
(1) 1 is a super ugly number for any given primes.
(2) The given numbers in primes are in ascending order.
(3) 0 < k ≤ 100, 0 < n ≤ 106, 0 < primes[i] < 1000.

Credits:
Special thanks to @peisi for adding this problem and creating all test cases.

public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        int[] ret = new int[n];
        ret[0] = 1;

        int[] indexes  = new int[primes.length];
   
        for(int i = 1; i < n; i++){
            ret[i] = Integer.MAX_VALUE;
   
            for(int j = 0; j < primes.length; j++) {
                if (primes[j] * ret[indexes[j]] < ret[i]) {
                    ret[i] = primes[j] * ret[indexes[j]];
                }
            }
   
            for(int j = 0; j < indexes.length; j++){
                if(ret[i] == primes[j] * ret[indexes[j]]){
                    indexes[j]++;
                }
            }
        }
   
        return ret[n - 1];
    }
}

Burst Balloons

Given n balloons, indexed from 0 to n-1. Each balloon is painted with a number on it represented by array nums. You are asked to burst all the balloons. If the you burst balloon i you will get nums[left] * nums[i] * nums[right] coins. Here left and right are adjacent indices of i. After the burst, the left and right then becomes adjacent.

Find the maximum coins you can collect by bursting the balloons wisely.

Note: 
(1) You may imagine nums[-1] = nums[n] = 1. They are not real therefore you can not burst them.
(2) 0 ≤ n ≤ 500, 0 ≤ nums[i] ≤ 100

Example:

Given [3, 1, 5, 8]

Return 167

    nums = [3,1,5,8] --> [3,5,8] -->   [3,8]   -->  [8]  --> []
   coins =  3*1*5      +  3*5*8    +  1*3*8      + 1*8*1   = 167

Credits:
Special thanks to @peisi for adding this problem and creating all test cases.

public class Solution {
    public int maxCoins(int[] nums) {
        if (nums == null || nums.length == 0) return 0;

        int[][] dp = new int[nums.length][nums.length];
        for (int len = 1; len <= nums.length; len++) {
            for (int start = 0; start <= nums.length - len; start++) {
                int end = start + len - 1;
                for (int i = start; i <= end; i++) {
                    int coins = nums[i] * getValue(nums, start - 1) * getValue(nums, end + 1);
                    coins += i != start ? dp[start][i - 1] : 0; // If not first one, we can add subrange on its left.
                    coins += i != end ? dp[i + 1][end] : 0; // If not last one, we can add subrange on its right
                    dp[start][end] = Math.max(dp[start][end], coins);
                }
            }
        }
        return dp[0][nums.length - 1];
    }

    private int getValue(int[] nums, int i) { // Deal with num[-1] and num[num.length]
        if (i < 0 || i >= nums.length) {
            return 1;
        }
        return nums[i];
    }
}

Sparse Matrix Multiplication

Given two sparse matrices A and B, return the result of AB.

You may assume that A's column number is equal to B's row number.

Example:

A = [
  [ 1, 0, 0],
  [-1, 0, 3]
]

B = [
  [ 7, 0, 0 ],
  [ 0, 0, 0 ],
  [ 0, 0, 1 ]
]


     |  1 0 0 |   | 7 0 0 |   |  7 0 0 |
AB = | -1 0 3 | x | 0 0 0 | = | -7 0 3 |
                  | 0 0 1 |

public class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        int m = A.length, n = A[0].length, nB = B[0].length;
        int[][] C = new int[m][nB];

        for(int i = 0; i < m; i++) {
            for(int k = 0; k < n; k++) {
                if (A[i][k] != 0) {
                    for (int j = 0; j < nB; j++) {
                        if (B[k][j] != 0) C[i][j] += A[i][k] * B[k][j];
                    }
                }
            }
        }
        return C;  
    }
}

Minimum Height Trees

For a undirected graph with tree characteristics, we can choose any node as the root. The result graph is then a rooted tree. Among all possible rooted trees, those with minimum height are called minimum height trees (MHTs). Given such a graph, write a function to find all the MHTs and return a list of their root labels.

Format
The graph contains n nodes which are labeled from 0 to n - 1. You will be given the number n and a list of undirected edges (each edge is a pair of labels).

You can assume that no duplicate edges will appear in edges. Since all edges are undirected, [0, 1] is the same as [1, 0] and thus will not appear together in edges.

Example 1:

Given n = 4, edges = [[1, 0], [1, 2], [1, 3]]

        0
        |
        1
       / \
      2   3

return [1]

Example 2:

Given n = 6, edges = [[0, 3], [1, 3], [2, 3], [4, 3], [5, 4]]

     0  1  2
      \ | /
        3
        |
        4
        |
        5

return [3, 4]

Hint:

1. How many MHTs can a graph have at most?

Note:

(1) According to the definition of tree on Wikipedia: “a tree is an undirected graph in which any two vertices are connected by exactly one path. In other words, any connected graph without simple cycles is a tree.”

(2) The height of a rooted tree is the number of edges on the longest downward path between the root and a leaf.

Credits:
Special thanks to @peisi for adding this problem and creating all test cases.

public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> res = new ArrayList<>();
        if (n == 0) {
            return res;
        }
        if (n == 1) {
            res.add(0);
            return res;
        }
        List<Set<Integer>> adjacent = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjacent.add(new HashSet<Integer>());
        }
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            adjacent.get(from).add(to);
            adjacent.get(to).add(from);
        }
        LinkedList<Integer> leaves = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (adjacent.get(i).size() == 1) {
                leaves.add(i);
            }
        }
        int numOfLeaves = n;
        while (numOfLeaves > 2) {
            numOfLeaves -= leaves.size();
            int count = leaves.size();
            while (count-- > 0) {
                int from = leaves.poll();
                int to = adjacent.get(from).iterator().next();
                adjacent.get(to).remove(from);
                if (adjacent.get(to).size() == 1) {
                    leaves.add(to);
                }
            }
        }
        return leaves;
    }
}

Best Time to Buy and Sell Stock with Cooldown

Say you have an array for which the i^th element is the price of a given stock on day i.
Design an algorithm to find the maximum profit. You may complete as many transactions as you like (ie, buy one and sell one share of the stock multiple times) with the following restrictions:

• You may not engage in multiple transactions at the same time (ie, you must sell the stock before you buy again).
• After you sell your stock, you cannot buy stock on next day. (ie, cooldown 1 day)

Example:

prices = [1, 2, 3, 0, 2]
maxProfit = 3
transactions = [buy, sell, cooldown, buy, sell]

Credits:
Special thanks to @peisi for adding this problem and creating all test cases.

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int n = prices.length;
        int buy[] = new int[n];
        int sell[] = new int[n];
        buy[0] = -prices[0];
        sell[0] = 0;
        for (int i = 1; i < prices.length; i++) {
            buy[i] = Math.max(buy[i - 1], (i == 1 ? 0 : sell[i - 2]) - prices[i]);
            sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);
        }
        return sell[n - 1];
    }
}

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length == 0) return 0;
        int n = prices.length;
        int buy = -prices[0];
        int sell = 0;
        int prevSell = 0;
       
        for (int i = 1; i < prices.length; i++) {
            int tmpBuy = buy;
            buy = Math.max(buy, prevSell - prices[i]);
            prevSell = sell;
            sell = Math.max(sell, tmpBuy + prices[i]);
        }
        return sell;
    }
}

Additive Number

Additive number is a string whose digits can form additive sequence.
A valid additive sequence should contain at least three numbers. Except for the first two numbers, each subsequent number in the sequence must be the sum of the preceding two.
For example:
"112358" is an additive number because the digits can form an additive sequence: 1, 1, 2, 3, 5, 8.

1 + 1 = 2, 1 + 2 = 3, 2 + 3 = 5, 3 + 5 = 8

"199100199" is also an additive number, the additive sequence is: 1, 99, 100, 199.

1 + 99 = 100, 99 + 100 = 199

Note: Numbers in the additive sequence cannot have leading zeros, so sequence 1, 2, 03 or 1, 02, 3 is invalid.
Given a string containing only digits '0'-'9', write a function to determine if it's an additive number.
Follow up:
How would you handle overflow for very large input integers?
Credits:
Special thanks to @jeantimex for adding this problem and creating all test cases


public class Solution {
    public boolean isAdditiveNumber(String num) {
        if (num == null || num.length() == 0) {
            return false;
        }
        return helper(num, 0, null, null);
    }
   
    private boolean helper(String num, int position, String pre2, String pre1) {
        if (pre2 != null && pre1 != null) {
            String sum = addTwoNumber(pre2, pre1);
            if (num.substring(position).startsWith(sum)) {
                if (num.length() == position + sum.length()) {
                    return true;
                } else if (num.length() > position + sum.length()) {
                    return helper(num, position + sum.length(), pre1, sum);
                }
            }
            return false;
        } else if (position < num.length()) {
            for (int i = position; i < num.length(); i++) {
                if (i != position && num.charAt(position) == '0') continue;
                if (pre2 == null) {
                    if (helper(num, i + 1, num.substring(position, i + 1), pre1)) return true;
                } else if (pre1 == null) {
                    if (helper(num, i + 1, pre2, num.substring(position, i + 1))) return true;
                }
            }
        }
        return false;
    }
   
    public String addTwoNumber(String str1, String str2) {
        StringBuilder sb = new StringBuilder();
        int p1 = str1.length() - 1;
        int p2 = str2.length() - 1;
        int carry = 0;
        while (p1 >= 0 || p2 >= 0 || carry != 0) {
            int val = carry;
            val += p1 >= 0 ? (str1.charAt(p1) - '0') : 0;
            val += p2 >= 0 ? (str2.charAt(p2) - '0') : 0;
            carry = val / 10;
            val %= 10;
            sb.append(val);
            p1--;
            p2--;
        }
        return sb.reverse().toString();
    }
}

Number of Islands II

A 2d grid map of m rows and n columns is initially filled with water. We may perform an addLand operation which turns the water at position (row, col) into a land. Given a list of positions to operate, count the number of islands after each addLand operation. An island is surrounded by water and is formed by connecting adjacent lands horizontally or vertically. You may assume all four edges of the grid are all surrounded by water.

Example:

Given m = 3, n = 3, positions = [[0,0], [0,1], [1,2], [2,1]].
Initially, the 2d grid grid is filled with water. (Assume 0 represents water and 1 represents land).

0 0 0
0 0 0
0 0 0

Operation #1: addLand(0, 0) turns the water at grid[0][0] into a land.

1 0 0
0 0 0   Number of islands = 1
0 0 0

Operation #2: addLand(0, 1) turns the water at grid[0][1] into a land.

1 1 0
0 0 0   Number of islands = 1
0 0 0

Operation #3: addLand(1, 2) turns the water at grid[1][2] into a land.

1 1 0
0 0 1   Number of islands = 2
0 0 0

Operation #4: addLand(2, 1) turns the water at grid[2][1] into a land.

1 1 0
0 0 1   Number of islands = 3
0 1 0

We return the result as an array: [1, 1, 2, 3]

Challenge:

Can you do it in time complexity O(k log mn), where k is the length of the positions?

public class Solution {
    public List<Integer> numIslands2(int m, int n, int[][] positions) {
        int[] roots = new int[m*n];
        Arrays.fill(roots, -1);
   
        int[] xOffset ={0, 0, 1, -1};
        int[] yOffset = {1, -1, 0, 0};
        List<Integer> result = new ArrayList<Integer>();
        for(int[] position : positions){
            int pointID = position[0]*n + position[1];
            roots[pointID] = pointID;
            int count = result.isEmpty()? 1 : result.get(result.size()-1) + 1;
            for(int i = 0; i < 4; i++){
                int newX = xOffset[i] + position[0];
                int newY = yOffset[i] + position[1];
                if(newX >= 0 && newX < m && newY >= 0 && newY < n && roots[newX * n + newY] != -1){
                    int root1 = find(newX * n + newY, roots);
                    if(root1 != pointID) count--;
                    roots[root1] = pointID;
                }
            }
            result.add(count);
        }
        return result;
    }
   
    public int find(int target, int[] roots){
        if(roots[target] == target) return target;
        return find(roots[target], roots);
    }
}