> For the complete documentation index, see [llms.txt](https://howardyangemail.gitbook.io/decode-leetcode/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://howardyangemail.gitbook.io/decode-leetcode/graph/topological-sort.md).

# Topological Sort

#### [207. Course Schedule](https://leetcode.com/problems/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.

{% tabs %}
{% tab title="Java" %}

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

{% endtab %}

{% tab title="Python" %}

```python
    def canFinish(self, numCourses: int, prerequisites: List[List[int]]) -> bool:
        graph = [[] for i in range(numCourses)]
        indegree = [0] * numCourses
        for v, u in prerequisites:
            graph[u].append(v)
            indegree[v] += 1
            
        queue = []
        for i in range(numCourses):
            if indegree[i] == 0:
                queue.append(i)
        visited = 0
        while queue:
            curt = queue.pop(0)
            visited += 1
            for next in graph[curt]:
                indegree[next] -= 1
                if indegree[next] == 0:
                    queue.append(next)
        return visited == numCourses
```

{% endtab %}
{% endtabs %}

#### [210. Course Schedule II](https://leetcode.com/problems/course-schedule-ii/)

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

{% tabs %}
{% tab title="Java" %}

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

{% endtab %}

{% tab title="Python" %}

```python
    def findOrder(self, numCourses: int, prerequisites: List[List[int]]) -> List[int]:
        graph = [[] for i in range(numCourses)]
        indegree = [0] * numCourses
        for v, u in prerequisites:
            graph[u].append(v)
            indegree[v] += 1
            
        queue = []
        for i in range(numCourses):
            if indegree[i] == 0:
                queue.append(i)
        res = []
        while queue:
            curt = queue.pop(0)
            res.append(curt)
            for next in graph[curt]:
                indegree[next] -= 1
                if indegree[next] == 0:
                    queue.append(next)
        if len(res) == numCourses:
            return res
        return []
```

{% endtab %}
{% endtabs %}

[1136. Parallel Courses](https://leetcode.com/problems/parallel-courses/)

```java
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](https://www.glassdoor.com/Interview/Write-a-function-to-calculate-build-order-given-a-project-with-a-list-of-dependencies-that-also-need-to-be-built-QTN_945371.htm)

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](https://leetcode.com/problems/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() : "";`

```java
    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](https://leetcode.com/problems/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.&#x20;

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.

```java
    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](https://leetcode.com/discuss/interview-question/326564/Google-or-Onsite-interview-or-Compress-2D-Array/302395)

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

```java
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.

```java
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);
            }
        }
    }
}
```

####