Leetcode: 326. Power of Three

Given an integer, write a function to determine if it is a power of three.

Follow up:
Could you do it without using any loop / recursion?

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

Brute-force Solution:
The problem asks for if there is a number n, where n = 3^x. So the brute-force solution is to try each x from 0 and see if 3^x is equal to n, until 3^x is greater than n then we return false.

Code (Java):

public class Solution {
    public boolean isPowerOfThree(int n) {
        if (n <= 0) {
            return false;
        }
        
        int i = 0;
        long cur = (long) Math.pow(3, i);
        long longN = (long) n;
        
        while (cur <= longN) {
            if (cur == longN) {
                return true;
            }
            
            i++;
            cur = (long) Math.pow(3, i);
        }
        
        return false;
    }
}

Some tricky solutions:

Method 2

If log10(n) / log10(3) returns an int (more precisely, a double but has 0 after decimal point), then n is a power of 3. (original post). But be careful here, you cannot use log (natural log) here, because it will generate round off error for n=243. This is more like a coincidence. I mean whenn=243, we have the following results:

log(243) = 5.493061443340548    log(3) = 1.0986122886681098
   ==> log(243)/log(3) = 4.999999999999999

log10(243) = 2.385606273598312    log10(3) = 0.47712125471966244
   ==> log10(243)/log10(3) = 5.0

This happens because log(3) is actually slightly larger than its true value due to round off, which makes the ratio smaller.

public boolean isPowerOfThree(int n) {
    return (Math.log10(n) / Math.log10(3)) % 1 == 0;
}

Editional Soluton:

Quick Navigation

• Solution
  • Approach #1 Loop Iteration [Accepted]
  • Approach #2 Base Conversion [Accepted]
  • Approach #3 Mathematics [Accepted]
  • Approach #4 Integer Limitations [Accepted]
• Performance Measurements
• Conclusion
• References

Solution

In this article we will look into ways of speeding up simple computations and why that is useful in practice.

---

Approach #1 Loop Iteration [Accepted]

One simple way of finding out if a number n is a power of a number b is to keep dividing n by b as long as the remainder is 0. This is because we can write

$$\begin{array}{cc}n& =b^x\\ n& =b\times b\times \dots \times b\end{array}$$

Hence it should be possible to divide n by b x times, every time with a remainder of 0 and the end result to be 1.

Java

public class Solution {
    public boolean isPowerOfThree(int n) {
        if (n < 1) {
            return false;
        }

        while (n % 3 == 0) {
            n /= 3;
        }

        return n == 1;    
    }
}

Notice that we need a guard to check that n != 0, otherwise the while loop will never finish. For negative numbers, the algorithm does not make sense, so we will include this guard as well.

Complexity Analysis

• Time complexity : $O(log_b(n))$. In our case that is $O(log_3n)$. The number of divisions is given by that logarithm.
• Space complexity : $O(1)$. We are not using any additional memory.

---

Approach #2 Base Conversion [Accepted]

In Base 10, all powers of 10 start with the digit 1 and then are followed only by 0 (e.g. 10, 100, 1000). This is true for other bases and their respective powers. For instance in base 2, the representations of $10_2$, $100_2$ and $1000_2$ are $2_{10}$, $4_{10}$ and $8_{10}$ respectively. Therefore if we convert our number to base 3 and the representation is of the form 100...0, then the number is a power of 3.

Proof

Given the base 3 representation of a number as the array s, with the least significant digit on index 0, the formula for converting from base 3 to base 10 is:

$\sum_{i=0}^{len(s) - 1} s[i] * 3^{i}$

Therefore, having just one digit of 1 and everything else 0 means the number is a power of 3.

Implementation

All we need to do is convert [4] the number to base 3 and check if it is written as a leading 1 followed by all 0.

A couple of built-in Java functions will help us along the way.

String baseChange = Integer.toString(number, base);

The code above converts number into base base and returns the result as a String. For example, Integer.toString(5, 2) == "101" andInteger.toString(5, 3) == "12".

boolean matches = myString.matches("123");

The code above checks if a certain Regular Expression[2] pattern exists inside a string. For instance the above will return true if the substring "123" exists inside the string myString.

boolean powerOfThree = baseChange.matches("^10*$")

We will use the regular expression above for checking if the string starts with 1 ^1, is followed by zero or more 0s 0* and contains nothing else $.

Java

public class Solution {
    public boolean isPowerOfThree(int n) {
        return Integer.toString(n, 3).matches("^10*$");
    }
}

Complexity Analysis

• Time complexity : $O(log_3n)$.
  Assumptions:
  • Integer.toString() - Base conversion is generally implemented as a repeated division. The complexity of should be similar to our approach #1:$O(log_3n)$.
  • String.matches() - Method iterates over the entire string. The number of digits in the base 3 representation of n is $O(log_3n)$.
• Space complexity : $O(log_3n)$.
  We are using two additional variables,
  • The string of the base 3 representation of the number (size $log_3n$)
  • The string of the regular expression (constant size)

---

Approach #3 Mathematics [Accepted]

We can use mathematics as follows

$$n=3^{i}i=lo{g}_3\left(n\right)i=\frac{lo{g}_b\left(n\right)}{lo{g}_b\left(3\right)}$$

n is a power of three if and only if i is an integer. In Java, we check if a number is an integer by taking the decimal part (using % 1) and checking if it is 0.

Java

public class Solution {
    public boolean isPowerOfThree(int n) {
        return (Math.log10(n) / Math.log10(3)) % 1 == 0;
    }
}

Common pitfalls

This solution is problematic because we start using doubles, which means we are subject to precision errors. This means, we should never use == when comparing doubles. That is because the result of Math.log10(n) / Math.log10(3) could be 5.0000001 or 4.9999999. This effect can be observed by using the function Math.log() instead of Math.log10().

In order to fix that, we need to compare the result against an epsilon.

Java

return (Math.log(n) / Math.log(3) + epsilon) % 1 <= 2 * epsilon;

Complexity Analysis

• Time complexity : $Unknown$ The expensive operation here is Math.log, which upper bounds the time complexity of our algorithm. The implementation is dependent on the language we are using and the compiler[3]
• Space complexity : $O(1)$. We are not using any additional memory. The epsilon variable can be inlined.

---

Approach #4 Integer Limitations [Accepted]

An important piece of information can be deduced from the function signature

public boolean isPowerOfThree(int n)

In particular, n is of type int. In Java, this means it is a 4 byte, signed integer [ref]. The maximum value of this data type is 2147483647. Three ways of calculating this value are

• Google
• System.out.println(Integer.MAX_VALUE);
• MaxInt = $\frac{ 2^{32} }{2} - 1$ since we use 32 bits to represent the number, half of the range is used for negative numbers and 0 is part of the positive numbers

Knowing the limitation of n, we can now deduce that the maximum value of n that is also a power of three is 1162261467. We calculate this as:

$3^{\lfloor{}log_3{MaxInt}\rfloor{}} = 3^{\lfloor{}19.56\rfloor{}} = 3^{19} = 1162261467$

Therefore, the possible values of n where we should return true are $3^0$, $3^1$ ... $3^{19}$. Since 3 is a prime number, the only divisors of $3^{19}$ are $3^0$, $3^1$ ... $3^{19}$, therefore all we need to do is divide $3^{19}$ by n. A remainder of 0 means n is a divisor of $3^{19}$ and therefore a power of three.

Java

public class Solution {
    public boolean isPowerOfThree(int n) {
        return n > 0 && 1162261467 % n == 0;
    }
}

Complexity Analysis

• Time complexity : $O(1)$. We are only doing one operation.
• Space complexity : $O(1)$. We are not using any additional memory.

Performance Measurements

Single runs of the function make it is hard to accurately measure the difference of the two solutions. On LeetCode, on the Accepted Solutions Runtime Distribution page, all solutions being between 15 ms and 20 ms. For completeness, we have proposed the following benchmark to see how the two solutions differ.

Java Benchmark Code

public static void main(String[] args) {
    Solution sol = new Solution();
    int iterations = 1; // See table header for this value
    for (int i = 0; i < iterations; i++) {
        sol.isPowerOfThree(i);
    }
}

In the table below, the values are in seconds.

Iterations	$10^6$	$10^7$	$10^8$	$10^9$	$Maxint$
Java Approach #1 (Naive)	0.04	0.07	0.30	2.47	5.26
Java Approach #2 (Strings)	0.68	4.02	38.90	409.16	893.89
Java Approach #3 (Logarithms)	0.09	0.50	4.59	45.53	97.50
Java Approach #4 (Fast)	0.04	0.06	0.08	0.41	0.78

As we can see, for small values of N, the difference is not noticeable, but as we do more iterations and the values of n passed to isPowerOfThree() grow, we see significant boosts in performance for Approach #4.

Conclusion

Simple optimizations like this might seem negligible, but historically, when computation power was an issue, it allowed certain computer programs (such as Quake 3[1]) possible.

References

• [1] https://en.wikipedia.org/wiki/Fast_inverse_square_root
• [2] https://en.wikipedia.org/wiki/Regular_expression
• [3] http://developer.classpath.org/doc/java/lang/StrictMath-source.html
• [4] http://www.cut-the-knot.org/recurrence/conversion.shtml

Leetcode: Maximum Size Subarray Sum Equals k

Given an array nums and a target value k, find the maximum length of a subarray that sums to k. If there isn't one, return 0 instead.

Example 1:

Given nums = [1, -1, 5, -2, 3], k = 3,
return 4. (because the subarray [1, -1, 5, -2] sums to 3 and is the longest)

Example 2:

Given nums = [-2, -1, 2, 1], k = 1,
return 2. (because the subarray [-1, 2] sums to 1 and is the longest)

Follow Up:
Can you do it in O(n) time?

Understand the problem:
The problem is equal to: find out a range from i to j, in which the sum (nums[i], ..., nums[j]) = k. What is the maximal range? 

So we can first calculate the prefix sum of each number, so sum(i, j) = sum(j) - sum(i - 1) = k. Therefore, for each sum(j), we only need to check if there was a sum(i - 1) which equals to sum(j) - k. We can use a hash map to store the previous calculated sum. 

Code (Java):

public class Solution {
    public int maxSubArrayLen(int[] nums, int k) {
        if(nums == null || nums.length == 0) {
            return 0;
        }
        
        int maxLen = 0;
        Map<Integer, Integer> map = new HashMap<>();
        map.put(0, -1); // IMPOARTANT
        int sum = 0;
        
        for (int i = 0; i < nums.length; i++) {
            sum += nums[i];
            if (!map.containsKey(sum)) {
                map.put(sum, i);
            }
            
            if (map.containsKey(sum - k)) {
                maxLen = Math.max(maxLen, i - map.get(sum - k));
            }
        }
        
        return maxLen;
    }
}

Comments:
Note the map.put(0, -1). We need to put this entry into the map before, because if the maximal range starts from 0, we need to calculate sum(j) - sum(i - 1). 

Leetcode: Number of Connected Components in an Undirected Graph

Given n nodes labeled from 0 to n - 1 and a list of undirected edges (each edge is a pair of nodes), write a function to find the number of connected components in an undirected graph.

Example 1:

     0          3
     |          |
     1 --- 2    4

Given n = 5 and edges = [[0, 1], [1, 2], [3, 4]], return 2.

Example 2:

     0           4
     |           |
     1 --- 2 --- 3

Given n = 5 and edges = [[0, 1], [1, 2], [2, 3], [3, 4]], return 1.

Note:
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.

DFS Solution:

public class Solution {
    public int countComponents(int n, int[][] edges) {
        if (n <= 0 || edges == null) {
            return 0;
        }
        
        if (n == 1 && edges.length == 0) {
            return 1;
        }
        
        int result = 0;
        boolean[] visited = new boolean[n];
        
        // step 1: create the adj list from edge list
        List[] adjList = new List[n];
        for (int i = 0; i < n; i++) {
            adjList[i] = new ArrayList<>();
        }
        
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            
            adjList[from].add(to);
            adjList[to].add(from);
        }
        
        // step 2: calculate the number of cc
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                result++;
                countCCHelper(i, adjList, visited);
            }
        }
        
        return result;
    }
    
    private void countCCHelper(int node, List[] adjList, boolean[] visited) {
        if (visited[node]) {
            return;
        }
        
        visited[node] = true;
        
        List<Integer> neighbors = adjList[node];
        
        for (int neighbor : neighbors) {
            countCCHelper(neighbor, adjList, visited);
        }
    }
}

A BFS Solution:

public class Solution {
    public int countComponents(int n, int[][] edges) {
        if (n <= 0 || edges == null) {
            return 0;
        }
        
        if (n == 1 && edges.length == 0) {
            return 1;
        }
        
        int result = 0;
        boolean[] visited = new boolean[n];
        
        // step 1: create the adj list from edge list
        List[] adjList = new List[n];
        for (int i = 0; i < n; i++) {
            adjList[i] = new ArrayList<>();
        }
        
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            
            adjList[from].add(to);
            adjList[to].add(from);
        }
        
        // step 2: calculate the number of cc
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                result++;
                countCCHelper(i, adjList, visited, queue);
            }
        }
        
        return result;
    }
    
    private void countCCHelper(int node, List[] adjList, boolean[] visited, Queue<Integer> queue) {
        fill(node, adjList, visited, queue);
        
        while (!queue.isEmpty()) {
            int currNode = queue.poll();
            List<Integer> neighbors = adjList[currNode];
            
            for (Integer neighbor : neighbors) {
                fill(neighbor, adjList, visited, queue);
            }
        }
    }
    
    private void fill(int node, List[] adjList, boolean[] visited, Queue<Integer> queue) {
        if (visited[node]) {
            return;
        }
        
        visited[node] = true;
        
        queue.offer(node);
    }
}

Union-find solution:

private int[] father;
public int countComponents(int n, int[][] edges) {

    Set<Integer> set = new HashSet<Integer>();
    father = new int[n];
    for (int i = 0; i < n; i++) {
        father[i] = i;
    }
    for (int i = 0; i < edges.length; i++) {
         union(edges[i][0], edges[i][1]);
    }

    for (int i = 0; i < n; i++){ 
        set.add(find(i));
    }
    return set.size();
}

int find(int node) {
    if (father[node] == node) {
        return node;
    }
    father[node] = find(father[node]);
    return father[node];
}

void union(int node1, int node2) {
    father[find(node1)] = find(node2);
}

Leetcode: 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 @dietpepsi for adding this problem and creating all test cases.

Understand the problem:
The idea is very similar to the problem Super ugly number II



Code (Java):

public class Solution {
    public int nthSuperUglyNumber(int n, int[] primes) {
        if (n == 1 || primes == null || primes.length == 0) {
            return 1;
        }
        
        int k = primes.length;
        int[] index = new int[k];
        
        List<Integer> result = new ArrayList<>();
        result.add(1);
        
        for (int i = 1; i < n; i++) {
            int curr = Integer.MAX_VALUE;
            for (int j = 0; j < k; j++) {
                curr = Math.min(curr, primes[j] * result.get(index[j]));
            }
            
            result.add(curr);
            
            // update the index
            for (int j = 0; j < k; j++) {
                if (primes[j] * result.get(index[j]) == curr) {
                    index[j]++;
                }
            }
        }
        
        return result.get(result.size() - 1);
    }
}

Analysis:
Time complexity is O(k * n), space complexity is O(n)

Leetcode: 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 |

Code (Java):

public class Solution {
    public int[][] multiply(int[][] A, int[][] B) {
        if (A == null || A.length == 0 ||
            B == null || B.length == 0) {
            return new int[0][0];    
        }
        
        int m = A.length;
        int n = A[0].length;
        int l = B[0].length;
        
        int[][] C = new int[m][l];
        
        // Step 1: convert the sparse A to dense format
        Map<Integer, Map<Integer, Integer>> denseA = new HashMap<>();
        for (int i = 0; i < m; i++) {
            for (int j = 0; j < n; j++) {
                if (A[i][j] != 0) {
                    if (!denseA.containsKey(i)) {
                        denseA.put(i, new HashMap<>());
                    }
                    denseA.get(i).put(j, A[i][j]);
                }
            }
        }
        
        // Step 2: convert the sparse B to dense format
        Map<Integer, Map<Integer, Integer>> denseB = new HashMap<>();
        for (int i = 0; i < n; i++) {
            for (int j = 0; j < l; j++) {
                if (B[i][j] != 0) {
                    if (!denseB.containsKey(i)) {
                        denseB.put(i, new HashMap<>());
                    }
                    denseB.get(i).put(j, B[i][j]);
                }
            }
        }
        
        // Step3: calculate the denseA * denseB
        for (int i : denseA.keySet()) {
            for (int j : denseA.get(i).keySet()) {
                if (!denseB.containsKey(j)) {
                    continue;
                }
                
                for (int k : denseB.get(j).keySet()) {
                    C[i][k] += denseA.get(i).get(j) * denseB.get(j).get(k);
                }
            }
        }
        
        return C;
    }
} 

Another solution using one table:
https://leetcode.com/discuss/71912/easiest-java-solution

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;   
    }
}

---

The followings is the original 75ms solution:

The idea is derived from a CMU lecture.

A sparse matrix can be represented as a sequence of rows, each of which is a sequence of (column-number, value) pairs of the nonzero values in the row.

So let's create a non-zero array for A, and do multiplication on B.

Hope it helps!

---

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

    List[] indexA = new List[m];
    for(int i = 0; i < m; i++) {
        List<Integer> numsA = new ArrayList<>();
        for(int j = 0; j < n; j++) {
            if(A[i][j] != 0){
                numsA.add(j); 
                numsA.add(A[i][j]);
            }
        }
        indexA[i] = numsA;
    }

    for(int i = 0; i < m; i++) {
        List<Integer> numsA = indexA[i];
        for(int p = 0; p < numsA.size() - 1; p += 2) {
            int colA = numsA.get(p);
            int valA = numsA.get(p + 1);
            for(int j = 0; j < nB; j ++) {
                int valB = B[colA][j];
                result[i][j] += valA * valB;
            }
        }
    }

    return result;   
}

Leetcode: 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]

Show Hint 

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 @dietpepsi for adding this problem and creating all test cases.

A brute-force O(n^2) solution:
A brute-force solution is we can construct the graph first, then for each vertex as a root of the tree, we calculate the height, and then compare the height with the minimum height we got so far. Update the minimum if necessary. Since getting the height of a tree takes O(n) time, and we need to traverse each vertex of the graph, the total time complexity is O(n^2). 

Code (Java):

public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> result = new ArrayList<>();
        if (n <= 0 || edges == null || edges.length == 0) {
            return result;
        }
        
        // Step 1: construct the adjList
        Map<Integer, List<Integer>> adjList = new HashMap<>();
        
        for (int[] edge : edges) {
            // add forward edge
            int from = edge[0];
            int to = edge[1];
            
            if (!adjList.containsKey(from)) {
                List<Integer> neighbors = new ArrayList<>();
                neighbors.add(to);
                adjList.put(from, neighbors); 
            } else {
                List<Integer> neighbors = adjList.get(from);
                neighbors.add(to);
                adjList.put(from, neighbors);
            }
            
            // Add the reverse edge
            if (!adjList.containsKey(to)) {
                List<Integer> neighbors = new ArrayList<>();
                neighbors.add(from);
                adjList.put(to, neighbors);
            } else {
                List<Integer> neighbors = adjList.get(to);
                neighbors.add(from);
                adjList.put(to, neighbors);
            }
        }
        
        // Step 2: iterate each vertex as the root and get the height
        boolean[] visited = new boolean[n];
        int minHeight = Integer.MAX_VALUE;
        
        for (int i = 0; i < n; i++) {
            int height = getHeightOfTree(i, adjList, visited);
            if (height < minHeight) {
                result.clear();
                result.add(i);
                minHeight = height;
            } else if (height == minHeight) {
                result.add(i);
            }
        }
        
        return result;
    }
    
    private int getHeightOfTree(int root, Map<Integer, List<Integer>> adjList, 
                                boolean[] visited) {
        List<Integer> neighbors = adjList.get(root);
        visited[root] = true;
        
        int maxHeight = 0;
        
        for (Integer neighbor : neighbors) {
            if (!visited[neighbor]) {
                maxHeight = Math.max(maxHeight, 
                  getHeightOfTree(neighbor, adjList, visited));
            }
        }
        
        visited[root] = false;
        
        return maxHeight + 1;
    }
}

A O(n) time solution:
https://leetcode.com/discuss/71763/share-some-thoughts

First let's review some statement for tree in graph theory:

(1) A tree is an undirected graph in which any two vertices are connected by exactly one path.

(2) Any connected graph who has n nodes with n-1 edges is a tree.

(3) The degree of a vertex of a graph is the number of edges incident to the vertex.

(4) A leaf is a vertex of degree 1. An internal vertex is a vertex of degree at least 2.

(5) A path graph is a tree with two or more vertices that is not branched at all.

(6) A tree is called a rooted tree if one vertex has been designated the root.

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

OK. Let's stop here and look at our problem.

Our problem want us to find the minimum height trees and return their root labels. First we can think about a simple case -- a path graph.

For a path graph of n nodes, find the minimum height trees is trivial. Just designate the middle point(s) as roots.

Despite its triviality, let design a algorithm to find them.

Suppose we don't know n, nor do we have random access of the nodes. We have to traversal. It is very easy to get the idea of two pointers. One from each end and move at the same speed. When they meet or they are one step away, (depends on the parity of n), we have the roots we want.

This gives us a lot of useful ideas to crack our real problem.

For a tree we can do some thing similar. We start from every end, by end we mean vertex of degree 1 (aka leaves). We let the pointers move the same speed. When two pointers meet, we keep only one of them, until the last two pointers meet or one step away we then find the roots.

It is easy to see that the last two pointers are from the two ends of the longest path in the graph.

The actual implementation is similar to the BFS topological sort. Remove the leaves, update the degrees of inner vertexes. Then remove the new leaves. Doing so level by level until there are 2 or 1 nodes left. What's left is our answer!

The time complexity and space complexity are both O(n).

Note that for a tree we always have V = n, E = n-1.

Code (Java):

public class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        List<Integer> result = new ArrayList<>();
        if (n <= 0) {
            return result;
        }
        
        // Corner case: there is a single node and no edge at all
        if (n == 1 && edges.length == 0) {
            result.add(0);
            return result;
        }
        
        // Step 1: construct the graph
        List<Set<Integer>> adjList = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            adjList.add(new HashSet<>());
        }
        
        for (int[] edge : edges) {
            int from = edge[0];
            int to = edge[1];
            adjList.get(from).add(to);
            adjList.get(to).add(from);
        }
        
        // Remove leaf nodes
        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (adjList.get(i).size() == 1) {
                leaves.add(i);
            }
        }
        
        while (n > 2) {
            // identify and remove all leaf nodes
            n -= leaves.size();
            List<Integer> newLeaves = new ArrayList<>();
            for (int leaf : leaves) {
                int neighbor = adjList.get(leaf).iterator().next();
                adjList.get(neighbor).remove(leaf);
                
                if (adjList.get(neighbor).size() == 1) {
                    newLeaves.add(neighbor);
                }
            }
            
            leaves = newLeaves;
        }
        
        return leaves;
    }
}

Summary:
1. Note in the implementation, we use List<Set<Integer>> to represent a adj list. That is because the vertex Id ranges from 0 to n - 1, we can use the list index to represent the vertex Id. 
2. In the implementation, we don't really delete the leaf nodes, which will result in an O(n) time since the adjList is a list. Instead, we find the leaf nodes in each iteration and remove it in the neighbor list. Then we find out the new leaf nodes.

Leetcode: Best Time to Buy and Sell Stock with Cooldown

Say you have an array for which the ith 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 @dietpepsi for adding this problem and creating all test cases.

Understand the problem:
https://leetcode.com/discuss/71391/easiest-java-solution-with-explanations

1. Define States

To represent the decision at index i:

• buy[i]: Max profit till index i. The series of transaction is ending with a buy.
• sell[i]: Max profit till index i. The series of transaction is ending with a sell.

To clarify:

• Till index i, the buy / sell action must happen and must be the last action. It may not happen at index i. It may happen at i - 1, i - 2, ... 0.
• In the end n - 1, return sell[n - 1]. Apparently we cannot finally end up with a buy. In that case, we would rather take a rest at n - 1.
• For special case no transaction at all, classify it as sell[i], so that in the end, we can still return sell[n - 1]. Thanks @alex153 @kennethliaoke @anshu2.

  ---

2. Define Recursion

• buy[i]: To make a decision whether to buy at i, we either take a rest, by just using the old decision at i - 1, or sell at/before i - 2, then buy at i, We cannot sell at i - 1, then buy at i, because of cooldown.
• sell[i]: To make a decision whether to sell at i, we either take a rest, by just using the old decision at i - 1, or buy at/before i - 1, then sell at i.

So we get the following formula:

buy[i] = Math.max(buy[i - 1], sell[i - 2] - prices[i]);   
sell[i] = Math.max(sell[i - 1], buy[i - 1] + prices[i]);

---

3. Optimize to O(1) Space

DP solution only depending on i - 1 and i - 2 can be optimized using O(1) space.

• Let b2, b1, b0 represent buy[i - 2], buy[i - 1], buy[i]
• Let s2, s1, s0 represent sell[i - 2], sell[i - 1], sell[i]

Then arrays turn into Fibonacci like recursion:

b0 = Math.max(b1, s2 - prices[i]);
s0 = Math.max(s1, b1 + prices[i]);

---

4. Write Code in 5 Minutes

First we define the initial states at i = 0:

• We can buy. The max profit at i = 0 ending with a buy is -prices[0].
• We cannot sell. The max profit at i = 0 ending with a sell is 0.

Code (Java):

public class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length <= 1) {
            return 0;
        }
        
        int b1 = -prices[0];
        
        int s2 = 0;
        int s1 = 0;
        
        for (int i = 1; i <= prices.length; i++) {
            int b0 = Math.max(b1, s2 - prices[i - 1]);
            int s0 = Math.max(s1, b1 + prices[i - 1]);
            
            b1 = b0;
            s2 = s1;
            s1 = s0;
        }
        
        return s1;
    }
}

Update on 10/25/18:

class Solution {
    public int maxProfit(int[] prices) {
        if (prices == null || prices.length < 2) {
            return 0;
        }
        
        int prevHold = -prices[0];
        int prevSold = 0;
        int prevRest = 0;
        
        for (int i = 1; i < prices.length; i++) {
            int currHold = Math.max(prevRest - prices[i], prevHold);
            int currSold = prevHold + prices[i];
            int currRest = Math.max(prevRest, prevSold);
            
            prevHold = currHold;
            prevSold = currSold;
            prevRest = currRest;
        }
        
        return Math.max(prevSold, prevRest);
    }
}

Leetcode: Remove Duplicate Letters

Given a string which contains only lowercase letters, remove duplicate letters so that every letter appear once and only once. You must make sure your result is the smallest in lexicographical order among all possible results.

Example:

Given "bcabc"
Return "abc"

Given "cbacdcbc"
Return "acdb"

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

Understand the problem:
https://leetcode.com/discuss/73777/easy-to-understand-iterative-java-solution

The basic idea is to find out the smallest result letter by letter (one letter at a time). Here is the thinking process for input "cbacdcbc":

1. find out the last appeared position for each letter; c - 7 b - 6 a - 2 d - 4
2. find out the smallest index from the map in step 1 (a - 2);
3. the first letter in the final result must be the smallest letter from index 0 to index 2;
4. repeat step 2 to 3 to find out remaining letters.

• the smallest letter from index 0 to index 2: a
• the smallest letter from index 3 to index 4: c
• the smallest letter from index 4 to index 4: d
• the smallest letter from index 5 to index 6: b

so the result is "acdb"

Notes:

• after one letter is determined in step 3, it need to be removed from the "last appeared position map", and the same letter should be ignored in the following steps
• in step 3, the beginning index of the search range should be the index of previous determined letter plus one

Code (Java):

public class Solution {
    public String removeDuplicateLetters(String s) {
        if (s == null || s.length() <= 1) {
            return s;
        }
        
        // Step 1: find the last index for each char
        Map<Character, Integer> lastIndexMap = new HashMap<>();
        for (int i = 0; i < s.length(); i++) {
            char c = s.charAt(i);
            lastIndexMap.put(c, i);
        }
        
        // Step 2: for each character, find the smallest index in the map
        // Then find out the smallest char before the index.
        StringBuilder sb = new StringBuilder();
        int start = 0;
        int end = findSmallestIndex(lastIndexMap);
        
        while (!lastIndexMap.isEmpty()) {
            char curr = 'z' + 1;
            int index = 0;
            for (int i = start; i <= end; i++) {
                char c = s.charAt(i);
                if ((c < curr) && (lastIndexMap.containsKey(c))) {
                    curr = c;
                    index = i;
                }
            }
            
            // append result
            sb.append(curr);
            lastIndexMap.remove(curr);
            
            // update the start and end
            start = index + 1;
            end = findSmallestIndex(lastIndexMap);
        }
        
        return sb.toString();
    }
    
    private int findSmallestIndex(Map<Character, Integer> lastIndexMap) {
        int result = Integer.MAX_VALUE;
        for (int index : lastIndexMap.values()) {
            result = Math.min(result, index);
        }
        
        return result;
    }
}