Topological Sort

207. Course Schedule

Count in-degrees of each node and build graph. Run Topological sort. Count the number of courses completed equals total number of courses.

Java

    public boolean canFinish(int numCourses, int[][] prerequisites) {
        Map<Integer, Set<Integer>> map = new HashMap<>();
        int[] indegree = new int[numCourses];
        for (int[] pre : prerequisites) {
            int from = pre[1], to = pre[0];
            map.putIfAbsent(from, new HashSet<>());
            map.get(from).add(to);
            indegree[to]++;
        }  
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                q.offer(i);
            }
        }
        while (!q.isEmpty()) {
            int curt = q.poll();
            numCourses--;
            for (int next : map.getOrDefault(curt, new HashSet<>())) {
                if (--indegree[next] == 0) {
                    q.offer(next);
                }
            }
        }
        return numCourses == 0;
    }

Python

210. Course Schedule II

Add visited courses to the list. Check if list size == numCourses before return.

Java

    public int[] findOrder(int numCourses, int[][] prerequisites) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        int[] indegree = new int[numCourses];
        for (int[] p : prerequisites) {
            graph.putIfAbsent(p[1], new HashSet<>());
            graph.get(p[1]).add(p[0]);
            indegree[p[0]]++;
        }
        Queue<Integer> q = new LinkedList<>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) q.offer(i);
        }
        List<Integer> list = new ArrayList<>();
        while (!q.isEmpty()) {
            int curt = q.poll();
            list.add(curt);
            if (!graph.containsKey(curt)) continue;
            for (int next : graph.get(curt)) {
                indegree[next]--;
                if (indegree[next] == 0) {
                    q.offer(next);
                }
            }
        }
        if (list.size() != numCourses) return new int[]{};
        int[] res = new int[numCourses];
        for (int i = 0; i < numCourses; i++) {
            res[i] = list.get(i);
        }
        return res;
    }

Python

1136. Parallel Courses

public int minimumSemesters(int n, int[][] relations) {
    Map<Integer, List<Integer>> graph = new HashMap<>();
    int[] indegree = new int[n + 1];
    for (int[] pair : relations) {
        graph.putIfAbsent(pair[0], new ArrayList<>());
        graph.get(pair[0]).add(pair[1]);
        indegree[pair[1]]++;
    }
    Queue<Integer> q = new LinkedList<>();
    for (int course = 1; course <= n; course++) {
        if (indegree[course] == 0) q.add(course);
    }
    if (q.isEmpty()) return -1;

    int res = 0, courseTaken = 0;
    while (!q.isEmpty()) {
        int size = q.size();
        res++;
        while (size-- > 0) {
            int curt = q.poll();
            courseTaken++;
            for (int next : graph.getOrDefault(curt, new ArrayList<>())) {
                if (--indegree[next] == 0) {
                    q.offer(next);
                }
            }
        }
    }
    return courseTaken == n ? res : -1;
}

Package Dependency

1. Given a dependency where for java packages p1,p2,p3

• p1:{p2,p3}

  p2:{p3}

  p3:{}

• This means p1 can be compiled when compilation of p2 and p3 done

• p2 can compile when p3 is compiled

• p3 can start as it does not have any dependence.

Write a function to calculate build order given a project with a list of dependencies that also need to be built.

269. Alien Dictionary

Build the graph. Store indegrees in a different map. Check if all chars are in the array by using return sb.length() == indegree.size() ? sb.toString() : "";

    public String alienOrder(String[] words) {
        if(words == null || words.length == 0) return "";
        Map<Character, Set<Character>> map = new HashMap<>();
        Map<Character, Integer> indegree = new HashMap<>();
        if (!buildGraph(map, indegree, words)) return "";
        Queue<Character> queue = new LinkedList<>();
        for (char key : indegree.keySet()) {
            if (indegree.get(key) == 0) {
                queue.offer(key);
            }
        }
        if (queue.isEmpty()) return "";
        StringBuilder sb = new StringBuilder();
        while (!queue.isEmpty()) {
            char curt = queue.poll();
            sb.append(curt);
            if (map.get(curt) == null) continue;
            for (char next : map.get(curt)) {
                indegree.put(next, indegree.get(next) - 1);
                if (indegree.get(next) == 0) {
                    queue.offer(next);
                }
            }
        }
        return sb.length() == indegree.size() ? sb.toString() : "";
    }
    
    private boolean buildGraph(Map<Character, Set<Character>> map,
                            Map<Character, Integer> indegree,
                            String[] words) {
        for (String word : words) {
            for (char c : word.toCharArray()) indegree.put(c, 0);
        }
        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i], w2 = words[i + 1];
            for (int k = 0; k < Math.min(w1.length(), w2.length()); k++) {
                char u = w1.charAt(k), v = w2.charAt(k);
                if (u != v) {
                    map.putIfAbsent(u, new HashSet<>());
                    if (!map.get(u).contains(v)) {
                        map.get(u).add(v);
                        indegree.put(v, indegree.getOrDefault(v, 0) + 1);
                    }
                    break;
                }
                if (k == Math.min(w1.length(), w2.length()) - 1 && w1.length() > w2.length()) {
                    return false;
                }
            }
        }
        return true;
    }

444. Sequence Reconstruction

Topological sort with lots of validations. Construct graph from provided sequences. Be care of when a sequence may exist multiple times, and there might be sequence with 1 size.

While traversing, check if the queue size > 1, this means there are multiple path. Also check if curt match with org[index++] and index is not out of bound.

As completed, check if traveled all nodes in org and graph.

    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        Map<Integer, Set<Integer>> graph = new HashMap<>();
        Map<Integer, Integer> indegree = new HashMap<>();
        for (List<Integer> s : seqs) {
            if (s.size() == 1) {
                int u = s.get(0);
                graph.putIfAbsent(u, new HashSet<>());
                indegree.put(u, indegree.getOrDefault(u, 0));
            } else {
                for (int i = 0; i < s.size() - 1; i++) {
                    int u = s.get(i), v = s.get(i + 1);
                    graph.putIfAbsent(u, new HashSet<>());
                    graph.putIfAbsent(v, new HashSet<>());
                    indegree.put(v, indegree.getOrDefault(v, 0));
                    indegree.put(u, indegree.getOrDefault(u, 0));
                    if (graph.get(u).add(v)) {
                        indegree.put(v, indegree.get(v) + 1);
                    }
                }
            }
        }

        Queue<Integer> q = new LinkedList<>();
        for (int key : indegree.keySet()) {
            if (indegree.get(key) == 0) {
                q.offer(key);
            }
        }
        int index = 0;
        while (!q.isEmpty()) {
            if (q.size() > 1) return false; // 精髓
            int curt = q.poll();
            if (index == org.length || curt != org[index++]) { 
                return false;
            }
            for (int next : graph.get(curt)) {
                indegree.put(next, indegree.get(next) - 1);
                if (indegree.get(next) == 0) {
                    q.offer(next);
                }
            }
        }
        return index == org.length && index == indegree.size();
    }

Compress 2D Array

Given a 2D array of distinct integers with n numbers, "compress" the array such that the resulting array's numbers are in the range [1, n] and their relative order is kept.

Relative order means that if a number at position (row1, col1) is smaller than a number at position (row2, col2) in the original array, it should still have that relationship in the resulting array.

Sort and reverse map the position and values.

public static int[][] compress2dArray(int[][] matrix) {
  PriorityQueue<Integer> pq = new PriorityQueue<>();
  for (int i = 0; i < matrix.length; i++) {
    for (int j = 0; j < matrix[0].length; j++) {
      pq.offer(matrix[i][j]);
    }
  }
  Map<Integer, Integer> map = new HashMap<>();
  int k = 1;
  while (!pq.isEmpty()) {
    map.put(pq.poll(), k++);
  }
  int[][] res = new int[matrix.length][matrix[0].length];
  for (int i = 0; i < matrix.length; i++) {
    for (int j = 0; j < matrix[0].length; j++) {
      res[i][j] = map.get(matrix[i][j]);
    }
  }
  return res;
}

Follow-up:

Compress the array to make the numbers as small as possible as long as the relative order holds true for numbers in the same row and column.

Build DAG and count indegree. Use Topological sort with Level order traversal to assign values.

class Node {
    int x,y,val;
    Node(int x, int y, int val) {
        this.x = x;
        this.y = y;
        this.val = val;
    }
}
public int[][] compress2dArray2(int[][] matrix) {
    Map<Node, Set<Node>> map = new HashMap<>();
    Map<Node, Integer> indegree = new HashMap<>();
    Node[][] nodes = new Node[matrix.length][matrix[0].length];
    buildGraph(matrix, nodes, map, indegree);
    Queue<Node> q = new LinkedList<>();
    int[][] res = new int[matrix.length][matrix[0].length];
    for (Node key : indegree.keySet()) {
        if (indegree.get(key) == 0) {
            q.offer(key);
        }
    }
    int i = 1;
    while (!q.isEmpty()) {
        for (int k = q.size(); k > 0 ; k--) {
            Node curt = q.poll();
            res[curt.x][curt.y] = i;
            if (map.get(curt) == null) continue;
            for (Node next : map.get(curt)) {
                indegree.put(next, indegree.get(next) - 1);
                if (indegree.get(next) == 0) {
                    q.offer(next);
                }
            }
        }
        i++;
    }
    return res;
}

public void buildGraph(int[][] matrix,
                       Node[][] nodes,
                       Map<Node, Set<Node>> map,
                       Map<Node, Integer> indegree) {
    int m = matrix.length, n = matrix[0].length;
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n; j++) {
            nodes[i][j] = new Node(i, j, matrix[i][j]);
        }
    }
    for (int i = 0; i < m - 1; i++) {
        for (int j = 0; j < n; j++) {
            Node up = nodes[i][j], down = nodes[i + 1][j];
            indegree.putIfAbsent(up, 0);
            indegree.putIfAbsent(down, 0);
            if (matrix[i][j] < matrix[i + 1][j]) {
                map.putIfAbsent(up, new HashSet<>());
                map.get(up).add(down);
                indegree.put(down, indegree.get(down) + 1);
            } else {
                map.putIfAbsent(down, new HashSet<>());
                map.get(down).add(up);
                indegree.put(up, indegree.get(up) + 1);
            }
        }
    }
    for (int i = 0; i < m; i++) {
        for (int j = 0; j < n - 1; j++) {
            Node left = nodes[i][j], right = nodes[i][j + 1];
            if (left.val < right.val) {
                map.putIfAbsent(left, new HashSet<>());
                map.get(left).add(right);
                indegree.put(right, indegree.get(right) + 1);
            } else {
                map.putIfAbsent(right, new HashSet<>());
                map.get(right).add(left);
                indegree.put(left, indegree.get(left) + 1);
            }
        }
    }
}