Question:

There are a total of n courses you have to take, labeled from 0 to n - 1.

Some courses may have prerequisites, for example to take course 0 you have to first take course 1, which is expressed as a pair: [0,1]

Given the total number of courses and a list of prerequisite pairs, is it possible for you to finish all courses?

For example:

2, [[1,0]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0. So it is possible.

2, [[1,0],[0,1]]
There are a total of 2 courses to take. To take course 1 you should have finished course 0, and to take course 0 you should also have finished course 1. So it is impossible.

Note:
The input prerequisites is a graph represented by a list of edges, not adjacency matrices. Read more about how a graph is represented.

click to show more hints.

Hints:
This problem is equivalent to finding if a cycle exists in a directed graph. If a cycle exists, no topological ordering exists and therefore it will be impossible to take all courses.
Topological Sort via DFS - A great video tutorial (21 minutes) on Coursera explaining the basic concepts of Topological Sort.
Topological sort could also be done via BFS.

Thinking:

We can search it from a arbitary node, can search by DFS. If there is a cycle, we will meet the visited nodes once DFS. So we need a array to hold the visited record. By the way, if we want a topological sort, we can hold a current value which is number of nodes initially and decrese one only when meet a sink node.

For BFS, we can find the nodes whose indegree or outdegree is zero, and search from them. If there is a cycle, the number of nodes searched will less than the exact number because in a cycle no nodes’ indegree or outdegree is zero.

Solution:

DFS:

public boolean canFinish(int numCourses, int[][] prerequisites) {
    if (numCourses <= 1)
        return true;
    ArrayList<HashSet<Integer>> edges = new ArrayList<HashSet<Integer>>(numCourses);
    boolean[] visited = new boolean[numCourses];

    for (int i = 0; i < numCourses; i++)
        edges.add(new HashSet<Integer>());

    for (int[] pre: prerequisites){
        edges.get(pre[0]).add(pre[1]);
    }

    for (int i = 0; i < numCourses; i++){
        if (edges.get(i).size() != 0)
            if (!dfs(edges, i, visited))
                return false;
    }

    return true;
}

private boolean dfs(ArrayList<HashSet<Integer>> edges, int i, boolean[] visited){
    if (visited[i] == true)
        return false;
    visited[i] = true;
    while (edges.get(i).size() != 0){
        int j = edges.get(i).iterator().next();

        if (!dfs(edges, j, visited))
            return false;

        edges.get(i).remove(j);
    }
    visited[i] = false; //there is a cycle only when once DFS, so we change it back when onece DFS is finished
    return true;
}

BFS:

    public boolean canFinishBFS(int numCourses, int[][] prerequisites) {
    if (numCourses <= 1)
        return true;
    ArrayList<HashSet<Integer>> edges = new ArrayList<HashSet<Integer>>(numCourses);
    int[] inDegree = new int[numCourses];
    Queue<Integer> q = new LinkedList<Integer>();
    int count = 0;

    for (int i = 0; i < numCourses; i++)
        edges.add(new HashSet<Integer>());

    for (int[] pre: prerequisites){
        if (!edges.get(pre[0]).contains(pre[1])){
            edges.get(pre[0]).add(pre[1]);
            inDegree[pre[1]]++;
        }
    }

    for (int i = 0; i < inDegree.length; i++)
        if (inDegree[i] == 0)
            q.add(i);

    while (!q.isEmpty()){
        int i = q.poll();
        count++;
        while (edges.get(i).size() != 0){
            int j = edges.get(i).iterator().next();
            if (--inDegree[j] == 0)
                q.add(j);
            edges.get(i).remove(j);
        }
    }

    return count == numCourses;
}

Simpler and more concise BFS solution:

Reference: https://leetcode.com/discuss/35578/easy-bfs-topological-sort-java

public boolean canFinish(int numCourses, int[][] prerequisites) {
    int[][] matrix = new int[numCourses][numCourses]; // i -> j
    int[] indegree = new int[numCourses];

    for (int i=0; i<prerequisites.length; i++) {
        int ready = prerequisites[i][0];
        int pre = prerequisites[i][1];
        if (matrix[pre][ready] == 0)
            indegree[ready]++; //duplicate case
        matrix[pre][ready] = 1;
    }

    int count = 0;
    Queue<Integer> queue = new LinkedList();
    for (int i=0; i<indegree.length; i++) {
        if (indegree[i] == 0) queue.offer(i);
    }
    while (!queue.isEmpty()) {
        int course = queue.poll();
        count++;
        for (int i=0; i<numCourses; i++) {
            if (matrix[course][i] != 0) {
                if (--indegree[i] == 0)
                    queue.offer(i);
            }
        }
    }
    return count == numCourses;
}

Question:

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:

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.

Thinking:

We should track the path from every leaves until there are only one or two nodes left. In other words, in the middle of the graph will be the root of the minimum height tree.

Solution:

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    if (n == 1){
        List<Integer> res = new ArrayList<Integer>();
        res.add(0);
        return res;
    }
    List<Integer> leaves = new ArrayList<Integer>();
    List<Set<Integer>> adj = new ArrayList<Set<Integer>>(n);
    for (int i = 0; i < n; i++)
        adj.add(new HashSet<Integer>());
    for (int[] edge: edges){
        adj.get(edge[0]).add(edge[1]);
        adj.get(edge[1]).add(edge[0]);
    }
    for (int i = 0; i < n; i++){
        if (adj.get(i).size() == 1)
            leaves.add(i);
    }

    while (n > 2){
        n -= leaves.size();
        List<Integer> newLeaves = new ArrayList<Integer>();
        for (int i: leaves){
            int j = adj.get(i).iterator().next();
            adj.get(j).remove(i);
            if (adj.get(j).size() == 1)
                newLeaves.add(j);
        }
        leaves = newLeaves;
    }

    return leaves;
}

Reference:https://leetcode.com/discuss/71763/share-some-thoughts

My previous code(LTE):

public List<Integer> findMinHeightTrees(int n, int[][] edges) {
    List<Integer> res = new ArrayList<Integer>();
    int min = Integer.MAX_VALUE;
    int res1 = -1;
    int res2 = -1;

    for (int i = 0; i < n; i++){
        int temp = bfs(n, i, edges);
        if (temp < min){
            min = temp;
            res1 = i;
        }
        else if (temp == min){
            res2 = i;
        }
    }

    if (res1 != -1)
        res.add(res1);
    if (res2 != -1)
        res.add(res2);

    return res;
}

private int bfs(int n, int i, int[][] edges){
    int height = 0;
    boolean[] used = new boolean[edges.length];
    Queue<Integer> q = new LinkedList<Integer>();
    q.add(i);

    while (!q.isEmpty()){
        int num = q.size();
        while (num > 0){
            int temp = q.poll();
            for (int j = 0; j < edges.length; j++){
                if (edges[j][0] == temp || edges[j][1] == temp){
                    if (used[j] == false){
                        if (edges[j][0] == temp)
                            q.add(edges[j][1]);
                        else
                            q.add(edges[j][0]);
                        used[j] = true;
                    }
                }
            }
            num--;
        }
        height++;
    }

    return height;
}

Question:

Implement next permutation, which rearranges numbers into the lexicographically next greater permutation of numbers.

If such arrangement is not possible, it must rearrange it as the lowest possible order (ie, sorted in ascending order).

The replacement must be in-place, do not allocate extra memory.

Here are some examples. Inputs are in the left-hand column and its corresponding outputs are in the right-hand column.

1,2,3 → 1,3,2
3,2,1 → 1,2,3
1,1,5 → 1,5,1

Thinking:

The method can be described as below:

Solution:

public void nextPermutation(int[] nums) {
    if (nums == null || nums.length == 0)
        return;
    int i = nums.length - 2;
    while (i >= 0 && nums[i] >= nums[i+1]){
        i--;
    }

    if (i == -1){
        reverse(nums, 0, nums.length-1);
        return;
    }

    int j = i+1;
    while (j < nums.length && nums[j] > nums[i]){
        j++;
    }
    j--;
    swap(nums, i, j);
    reverse(nums, i+1, nums.length-1);

    return;
}
private void swap(int[] nums, int i, int j){
    int temp = nums[i];
    nums[i] = nums[j];
    nums[j] = temp;
}
private void reverse(int[] nums, int i, int j){
    while (i < j){
        swap(nums, i++, j--);
    }
}

Reference:http://fisherlei.blogspot.com/2012/12/leetcode-next-permutation.html
http://www.cnblogs.com/springfor/p/3896245.html

Question:

Given an array of n positive integers and a positive integer s, find the minimal length of a subarray of which the sum ≥ s. If there isn’t one, return 0 instead.

For example, given the array [2,3,1,2,4,3] and s = 7,
the subarray [4,3] has the minimal length under the problem constraint.

click to show more practice.

More practice:
If you have figured out the O(n) solution, try coding another solution of which the time complexity is O(n log n).

Thinking:

My method is to hold two pointers, one for current index and the other is for the start pointer. Once we find the sum is bigger than target, we increse the startIndex until its sum is smaller than target. Do it while find the minmun of the length.

But there is still more effienct way to solve this problem. We don’t need to reset the startIndex and sum, we just keep it. And it will be the O(n) solution. (Which called a minmum window method I suppose.)

What’s more, binary search is also valid for this problem. Since all elements are positive, the cumulative sum must be strictly increasing. Then, a subarray sum can expressed as the difference between two cumulative sum. Hence, given a start index for the cumulative sum array, the other end index can be searched using binary search.

Solution:

First version:

public int minSubArrayLen(int s, int[] nums) {
    int min = Integer.MAX_VALUE;
    boolean flag = false;
    int temp = 0;
    int startIndex = 0;

    for ( int i = 0; i < nums.length; i++ ){
         temp += nums[i];
         if (temp >= s){
             while (temp >= s){
                 flag = true;
                 temp -= nums[startIndex++];
             }
             int len = i - startIndex + 2;
             i = startIndex-1;
             if (len < min)
                 min = len;
             temp = 0;
         }

    }
    if (flag)
        return min;
    else
        return 0;
}

Revised version:

public int minSubArrayLen(int s, int[] nums) {
    int min = Integer.MAX_VALUE;
    boolean flag = false;
    int temp = 0;
    int startIndex = 0;

    for ( int i = 0; i < nums.length; i++ ){
         temp += nums[i];
         if (temp >= s){
             while (temp >= s){
                 flag = true;
                 temp -= nums[startIndex++];
             }
             int len = i - startIndex + 2;
             if (len < min)
                 min = len;
         }

    }
    if (flag)
        return min;
    else
        return 0;
}

Reference Code:(Including O(n) and O(nlgn))
Reference:https://leetcode.com/discuss/35378/solutions-java-with-time-complexity-nlogn-with-explanation

public int minSubArrayLen(int s, int[] nums) {
    return solveNLogN(s, nums);
}

private int solveN(int s, int[] nums) {
    int start = 0, end = 0, sum = 0, minLen = Integer.MAX_VALUE;
    while (end < nums.length) {
        while (end < nums.length && sum < s) sum += nums[end++];
        if (sum < s) break;
        while (start < end && sum >= s) sum -= nums[start++];
        if (end - start + 1 < minLen) minLen = end - start + 1;
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

private int solveNLogN(int s, int[] nums) {
    int[] sums = new int[nums.length + 1];
    for (int i = 1; i < sums.length; i++) sums[i] = sums[i - 1] + nums[i - 1];
    int minLen = Integer.MAX_VALUE;
    for (int i = 0; i < sums.length; i++) {
        int end = binarySearch(i + 1, sums.length - 1, sums[i] + s, sums);
        if (end == sums.length) break;
        if (end - i < minLen) minLen = end - i;
    }
    return minLen == Integer.MAX_VALUE ? 0 : minLen;
}

private int binarySearch(int lo, int hi, int key, int[] sums) {
    while (lo <= hi) {
       int mid = (lo + hi) / 2;
       if (sums[mid] >= key){
           hi = mid - 1;
       } else {
           lo = mid + 1;
       }
    }
    return lo;
}

Question:

Write a program to find the n-th ugly number.

Ugly numbers are positive numbers whose prime factors only include 2, 3, 5. For example, 1, 2, 3, 4, 5, 6, 8, 9, 10, 12 is the sequence of the first 10 ugly numbers.

Note that 1 is typically treated as an ugly number.

Hint:

The naive approach is to call isUgly for every number until you reach the nth one. Most numbers are not ugly. Try to focus your effort on generating only the ugly ones.
An ugly number must be multiplied by either 2, 3, or 5 from a smaller ugly number.
The key is how to maintain the order of the ugly numbers. Try a similar approach of merging from three sorted lists: L1, L2, and L3.
Assume you have Uk, the kth ugly number. Then Uk+1 must be Min(L1 2, L2 3, L3 * 5).

Thinking:

The main idea of this question is to maintain a min heap and get the minimum from the heap once. Because we can see that, the ugly numbers are as below:

(1) 1×2, 2×2, 3×2, 4×2, 5×2, …
(2) 1×3, 2×3, 3×3, 4×3, 5×3, …
(3) 1×5, 2×5, 3×5, 4×5, 5×5, …

Furthermore, we can record different factor’s index in the primes in order to make the algorithm more effienct.

Solution:

(LTE)

public int nthUglyNumber1(int n){
    List<Integer> res = new ArrayList<Integer>();
    PriorityQueue<Integer> heap = new PriorityQueue<Integer>();
    heap.add(1);
    int[] primes = {2, 3, 5};
    while (res.size() != n) {
        int num = heap.poll();
        if (res.size() == 0 || num != res.get(res.size()-1))
            res.add(num);
        for ( int j = 0; j < 3; j++){
            heap.add(num * primes[j]);
        }
    }

    return res.get(n-1);
}

(AC)

public int nthUglyNumber2(int n) {
    List<Integer> res = new ArrayList<Integer>();
    res.add(1);
    int[] index = new int[3];
    int[] list = new int[3];
    int[] primes = {2, 3, 5};
    list[0] = 1;
    list[1] = 1;
    list[2] = 1;

    for (int i = 1; i < n; i++){
        for (int j = 0; j < 3; j++){
            list[j] = res.get(index[j]) * primes[j];
        }
        res.add(Math.min(Math.min(list[0], list[1]), list[2]));
        for (int j = 0; j < 3; j++){
            if (list[j] == res.get(res.size()-1))
                index[j]++;
        }
    }

    return res.get(n-1);
}

Reference: https://leetcode.com/discuss/52716/o-n-java-solution