Problems

Topological sort problems usually present themselves as scheduling tasks, resolving dependencies, or determining a valid ordering of elements. These problems typically involve processing directed graphs to find a sequence that respects all edges.

If you need a refresher on the implementation detail, check out our Code Templates.

Easy

1. Course Schedule

LeetCode 207

Brief: Determine if it is possible to finish all courses given a list of prerequisites.
Why this pattern?: This is the classic application of Topological Sort. A cycle in the graph means some courses can never be finished.
Key Insight: Use Kahn’s algorithm to resolve dependencies. If the number of processed nodes is less than the total number of courses, a cycle exists. Complexity is
O(V + E)
.

  flowchart LR
    0((0)) --> 1((1))
    1((1)) --> 0((0))
    style 0 fill:#fdd,stroke:#f66
    style 1 fill:#fdd,stroke:#f66

JavaScript:

function canFinish(numCourses, prerequisites) {
    const adj = Array.from({ length: numCourses }, () => []);
    const indegree = new Array(numCourses).fill(0);

    for (const [course, prereq] of prerequisites) {
        adj[prereq].push(course);
        indegree[course]++;
    }

    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (indegree[i] === 0) queue.push(i);
    }

    let count = 0;
    while (queue.length > 0) {
        const u = queue.shift();
        count++;
        for (const v of adj[u]) {
            indegree[v]--;
            if (indegree[v] === 0) queue.push(v);
        }
    }

    return count === numCourses;
}

Python:

from collections import deque

def canFinish(numCourses, prerequisites):
    adj = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses

    for course, prereq in prerequisites:
        adj[prereq].append(course)
        indegree[course] += 1

    queue = deque([i for i in range(numCourses) if indegree[i] == 0])
    count = 0

    while queue:
        u = queue.popleft()
        count += 1
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    return count == numCourses

Java:

class Solution {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        int[] indegree = new int[numCourses];
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());

        for (int[] p : prerequisites) {
            adj.get(p[1]).add(p[0]);
            indegree[p[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }

        int count = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            count++;
            for (int v : adj.get(u)) {
                if (--indegree[v] == 0) queue.offer(v);
            }
        }

        return count == numCourses;
    }
}

C++:

class Solution {
public:
    bool canFinish(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adj(numCourses);
        vector<int> indegree(numCourses, 0);

        for (auto& p : prerequisites) {
            adj[p[1]].push_back(p[0]);
            indegree[p[0]]++;
        }

        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) q.push(i);
        }

        int count = 0;
        while (!q.empty()) {
            int u = q.front(); q.pop();
            count++;
            for (int v : adj[u]) {
                if (--indegree[v] == 0) q.push(v);
            }
        }

        return count == numCourses;
    }
};

Go:

func canFinish(numCourses int, prerequisites [][]int) bool {
    adj := make([][]int, numCourses)
    indegree := make([]int, numCourses)

    for _, p := range prerequisites {
        adj[p[1]] = append(adj[p[1]], p[0])
        indegree[p[0]]++
    }

    queue := []int{}
    for i := 0; i < numCourses; i++ {
        if indegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    count := 0
    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        count++
        for _, v := range adj[u] {
            indegree[v]--
            if indegree[v] == 0 {
                queue = append(queue, v)
            }
        }
    }

    return count == numCourses
}

Ruby:

def can_finish(num_courses, prerequisites)
  adj = Array.new(num_courses) { [] }
  indegree = Array.new(num_courses, 0)

  prerequisites.each do |course, prereq|
    adj[prereq] << course
    indegree[course] += 1
  end

  queue = []
  num_courses.times { |i| queue << i if indegree[i] == 0 }

  count = 0
  while !queue.empty?
    u = queue.shift
    count += 1
    adj[u].each do |v|
      indegree[v] -= 1
      queue << v if indegree[v] == 0
    end
  end

  count == num_courses
end

Medium

2. Course Schedule II

LeetCode 210

Brief: Return a valid ordering of courses to finish all courses. Return an empty array if impossible.
Why this pattern?: This problem explicitly asks for the linear ordering produced by a topological sort.
Key Insight: The order in which nodes are added to the result list in Kahn’s algorithm is a valid topological order. Space complexity is
O(V + E)
.

  flowchart TD
    1((1)) --> 0((0))
    2((2)) --> 0((0))
    3((3)) --> 1((1))
    3((3)) --> 2((2))
    style 3 fill:#bfb,stroke:#090

JavaScript:

function findOrder(numCourses, prerequisites) {
    const adj = Array.from({ length: numCourses }, () => []);
    const indegree = new Array(numCourses).fill(0);
    const result = [];

    for (const [course, prereq] of prerequisites) {
        adj[prereq].push(course);
        indegree[course]++;
    }

    const queue = [];
    for (let i = 0; i < numCourses; i++) {
        if (indegree[i] === 0) queue.push(i);
    }

    while (queue.length > 0) {
        const u = queue.shift();
        result.push(u);
        for (const v of adj[u]) {
            indegree[v]--;
            if (indegree[v] === 0) queue.push(v);
        }
    }

    return result.length === numCourses ? result : [];
}

Python:

from collections import deque

def findOrder(numCourses, prerequisites):
    adj = [[] for _ in range(numCourses)]
    indegree = [0] * numCourses
    result = []

    for course, prereq in prerequisites:
        adj[prereq].append(course)
        indegree[course] += 1

    queue = deque([i for i in range(numCourses) if indegree[i] == 0])

    while queue:
        u = queue.popleft()
        result.append(u)
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    return result if len(result) == numCourses else []

Java:

class Solution {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        int[] indegree = new int[numCourses];
        int[] result = new int[numCourses];
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());

        for (int[] p : prerequisites) {
            adj.get(p[1]).add(p[0]);
            indegree[p[0]]++;
        }

        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) queue.offer(i);
        }

        int index = 0;
        while (!queue.isEmpty()) {
            int u = queue.poll();
            result[index++] = u;
            for (int v : adj.get(u)) {
                if (--indegree[v] == 0) queue.offer(v);
            }
        }

        return index == numCourses ? result : new int[0];
    }
}

C++:

class Solution {
public:
    vector<int> findOrder(int numCourses, vector<vector<int>>& prerequisites) {
        vector<vector<int>> adj(numCourses);
        vector<int> indegree(numCourses, 0);
        vector<int> result;

        for (auto& p : prerequisites) {
            adj[p[1]].push_back(p[0]);
            indegree[p[0]]++;
        }

        queue<int> q;
        for (int i = 0; i < numCourses; i++) {
            if (indegree[i] == 0) q.push(i);
        }

        while (!q.empty()) {
            int u = q.front(); q.pop();
            result.push_back(u);
            for (int v : adj[u]) {
                if (--indegree[v] == 0) q.push(v);
            }
        }

        return result.size() == numCourses ? result : vector<int>();
    }
};

Go:

func findOrder(numCourses int, prerequisites [][]int) []int {
    adj := make([][]int, numCourses)
    indegree := make([]int, numCourses)
    result := make([]int, 0, numCourses)

    for _, p := range prerequisites {
        adj[p[1]] = append(adj[p[1]], p[0])
        indegree[p[0]]++
    }

    queue := []int{}
    for i := 0; i < numCourses; i++ {
        if indegree[i] == 0 {
            queue = append(queue, i)
        }
    }

    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        result = append(result, u)
        for _, v := range adj[u] {
            indegree[v]--
            if indegree[v] == 0 {
                queue = append(queue, v)
            }
        }
    }

    if len(result) == numCourses {
        return result
    }
    return []int{}
}

Ruby:

def find_order(num_courses, prerequisites)
  adj = Array.new(num_courses) { [] }
  indegree = Array.new(num_courses, 0)
  result = []

  prerequisites.each do |course, prereq|
    adj[prereq] << course
    indegree[course] += 1
  end

  queue = []
  num_courses.times { |i| queue << i if indegree[i] == 0 }

  while !queue.empty?
    u = queue.shift
    result << u
    adj[u].each do |v|
      indegree[v] -= 1
      queue << v if indegree[v] == 0
    end
  end

  result.length == num_courses ? result : []
end

3. Alien Dictionary

LeetCode 269

Brief: Given a list of sorted alien words, derive the character order.
Why this pattern?: Adjacent words reveal relative ordering of characters (e.g., “aba” < “abc” implies ‘a’ < ‘c’).
Key Insight: Build the graph character by character. Note the edge case where a prefix comes after its extension (e.g., “apple” before “app”), which is invalid. Time complexity is
O(C)
where C is total characters in words.

  flowchart LR
    w((w)) --> e((e))
    e((e)) --> r((r))
    r((r)) --> t((t))
    t((t)) --> f((f))

JavaScript:

function alienOrder(words) {
    const adj = new Map();
    const indegree = new Map();
    for (const word of words) {
        for (const char of word) {
            if (!adj.has(char)) {
                adj.set(char, new Set());
                indegree.set(char, 0);
            }
        }
    }

    for (let i = 0; i < words.length - 1; i++) {
        const w1 = words[i], w2 = words[i+1];
        if (w1.length > w2.length && w1.startsWith(w2)) return "";
        for (let j = 0; j < Math.min(w1.length, w2.length); j++) {
            if (w1[j] !== w2[j]) {
                if (!adj.get(w1[j]).has(w2[j])) {
                    adj.get(w1[j]).add(w2[j]);
                    indegree.set(w2[j], indegree.get(w2[j]) + 1);
                }
                break;
            }
        }
    }

    const queue = [];
    for (const [char, count] of indegree) {
        if (count === 0) queue.push(char);
    }

    let res = "";
    while (queue.length > 0) {
        const u = queue.shift();
        res += u;
        for (const v of adj.get(u)) {
            indegree.set(v, indegree.get(v) - 1);
            if (indegree.get(v) === 0) queue.push(v);
        }
    }

    return res.length === adj.size ? res : "";
}

Python:

from collections import deque

def alienOrder(words):
    adj = {c: set() for w in words for c in w}
    indegree = {c: 0 for w in words for c in w}

    for i in range(len(words) - 1):
        w1, w2 = words[i], words[i+1]
        min_len = min(len(w1), len(w2))
        if len(w1) > len(w2) and w1[:min_len] == w2[:min_len]:
            return ""
        for j in range(min_len):
            if w1[j] != w2[j]:
                if w2[j] not in adj[w1[j]]:
                    adj[w1[j]].add(w2[j])
                    indegree[w2[j]] += 1
                break

    queue = deque([c for c in indegree if indegree[c] == 0])
    res = []
    while queue:
        u = queue.popleft()
        res.append(u)
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    return "".join(res) if len(res) == len(adj) else ""

Java:

class Solution {
    public String alienOrder(String[] words) {
        Map<Character, Set<Character>> adj = new HashMap<>();
        Map<Character, Integer> indegree = new HashMap<>();
        for (String w : words) {
            for (char c : w.toCharArray()) {
                adj.putIfAbsent(c, new HashSet<>());
                indegree.putIfAbsent(c, 0);
            }
        }

        for (int i = 0; i < words.length - 1; i++) {
            String w1 = words[i], w2 = words[i+1];
            if (w1.length() > w2.length() && w1.startsWith(w2)) return "";
            for (int j = 0; j < Math.min(w1.length(), w2.length()); j++) {
                if (w1.charAt(j) != w2.charAt(j)) {
                    if (adj.get(w1.charAt(j)).add(w2.charAt(j))) {
                        indegree.put(w2.charAt(j), indegree.get(w2.charAt(j)) + 1);
                    }
                    break;
                }
            }
        }

        Queue<Character> q = new LinkedList<>();
        for (char c : indegree.keySet()) {
            if (indegree.get(c) == 0) q.offer(c);
        }

        StringBuilder sb = new StringBuilder();
        while (!q.isEmpty()) {
            char u = q.poll();
            sb.append(u);
            for (char v : adj.get(u)) {
                indegree.put(v, indegree.get(v) - 1);
                if (indegree.get(v) == 0) q.offer(v);
            }
        }

        return sb.length() == adj.size() ? sb.toString() : "";
    }
}

C++:

class Solution {
public:
    string alienOrder(vector<string>& words) {
        unordered_map<char, unordered_set<char>> adj;
        unordered_map<char, int> indegree;
        for (auto& w : words) {
            for (char c : w) {
                if (adj.find(c) == adj.end()) {
                    adj[c] = unordered_set<char>();
                    indegree[c] = 0;
                }
            }
        }

        for (int i = 0; i < words.size() - 1; i++) {
            string w1 = words[i], w2 = words[i+1];
            if (w1.size() > w2.size() && w1.substr(0, w2.size()) == w2) return "";
            for (int j = 0; j < min(w1.size(), w2.size()); j++) {
                if (w1[j] != w2[j]) {
                    if (adj[w1[j]].insert(w2[j]).second) {
                        indegree[w2[j]]++;
                    }
                    break;
                }
            }
        }

        queue<char> q;
        for (auto& pair : indegree) {
            if (pair.second == 0) q.push(pair.first);
        }

        string res = "";
        while (!q.empty()) {
            char u = q.front(); q.pop();
            res += u;
            for (char v : adj[u]) {
                if (--indegree[v] == 0) q.push(v);
            }
        }

        return res.size() == adj.size() ? res : "";
    }
};

Go:

func alienOrder(words []string) string {
    adj := make(map[byte]map[byte]bool)
    indegree := make(map[byte]int)
    for _, w := range words {
        for i := 0; i < len(w); i++ {
            if _, exists := adj[w[i]]; !exists {
                adj[w[i]] = make(map[byte]bool)
                indegree[w[i]] = 0
            }
        }
    }

    for i := 0; i < len(words)-1; i++ {
        w1, w2 := words[i], words[i+1]
        minLen := len(w1)
        if len(w2) < minLen { minLen = len(w2) }
        if len(w1) > len(w2) && w1[:minLen] == w2[:minLen] { return "" }
        for j := 0; j < minLen; j++ {
            if w1[j] != w2[j] {
                if !adj[w1[j]][w2[j]] {
                    adj[w1[j]][w2[j]] = true
                    indegree[w2[j]]++
                }
                break
            }
        }
    }

    queue := []byte{}
    for char, count := range indegree {
        if count == 0 { queue = append(queue, char) }
    }

    res := []byte{}
    for len(queue) > 0 {
        u := queue[0]
        queue = queue[1:]
        res = append(res, u)
        for v := range adj[u] {
            indegree[v]--
            if indegree[v] == 0 { queue = append(queue, v) }
        }
    }

    if len(res) == len(adj) { return string(res) }
    return ""
}

Ruby:

def alien_order(words)
  adj = {}
  indegree = {}
  words.each do |w|
    w.each_char do |c|
      adj[c] ||= Set.new
      indegree[c] ||= 0
    end
  end

  (words.length - 1).times do |i|
    w1, w2 = words[i], words[i+1]
    min_len = [w1.length, w2.length].min
    return "" if w1.length > w2.length && w1[0...min_len] == w2
    min_len.times do |j|
      if w1[j] != w2[j]
        unless adj[w1[j]].include?(w2[j])
          adj[w1[j]] << w2[j]
          indegree[w2[j]] += 1
        end
        break
      end
    end
  end

  queue = indegree.select { |_, v| v == 0 }.keys
  res = ""
  while !queue.empty?
    u = queue.shift
    res += u
    adj[u].each do |v|
      indegree[v] -= 1
      queue << v if indegree[v] == 0
    end
  end

  res.length == adj.length ? res : ""
end

Hard

4. Minimum Height Trees

LeetCode 310

Brief: Find all nodes that, when chosen as root, result in a tree with minimum height.
Why this pattern?: This is a “top-down” topological sort. We peel off leaf nodes layer by layer until the center is reached.
Key Insight: Only 1 or 2 nodes can be the center of a tree. We iteratively remove nodes with degree 1. Time complexity is
O(V)
.

  flowchart TD
    A((A)) --- B((B))
    B((B)) --- C((C))
    B((B)) --- D((D))
    C((C)) --- E((E))
    style B fill:#bfb,stroke:#090
    style C fill:#bfb,stroke:#090

JavaScript:

function findMinHeightTrees(n, edges) {
    if (n === 1) return [0];
    const adj = Array.from({ length: n }, () => new Set());
    for (const [u, v] of edges) {
        adj[u].add(v);
        adj[v].add(u);
    }

    let leaves = [];
    for (let i = 0; i < n; i++) {
        if (adj[i].size === 1) leaves.push(i);
    }

    let remainingNodes = n;
    while (remainingNodes > 2) {
        remainingNodes -= leaves.length;
        const newLeaves = [];
        for (const leaf of leaves) {
            const neighbor = adj[leaf].values().next().value;
            adj[neighbor].delete(leaf);
            if (adj[neighbor].size === 1) newLeaves.push(neighbor);
        }
        leaves = newLeaves;
    }

    return leaves;
}

Python:

def findMinHeightTrees(n, edges):
    if n <= 2:
        return [i for i in range(n)]

    adj = [set() for _ in range(n)]
    for u, v in edges:
        adj[u].add(v)
        adj[v].add(u)

    leaves = [i for i in range(n) if len(adj[i]) == 1]

    remaining_nodes = n
    while remaining_nodes > 2:
        remaining_nodes -= len(leaves)
        new_leaves = []
        for leaf in leaves:
            neighbor = adj[leaf].pop()
            adj[neighbor].remove(leaf)
            if len(adj[neighbor]) == 1:
                new_leaves.append(neighbor)
        leaves = new_leaves

    return leaves

Java:

class Solution {
    public List<Integer> findMinHeightTrees(int n, int[][] edges) {
        if (n <= 2) {
            List<Integer> res = new ArrayList<>();
            for (int i = 0; i < n; i++) res.add(i);
            return res;
        }

        Set<Integer>[] adj = new Set[n];
        for (int i = 0; i < n; i++) adj[i] = new HashSet<>();
        for (int[] e : edges) {
            adj[e[0]].add(e[1]);
            adj[e[1]].add(e[0]);
        }

        List<Integer> leaves = new ArrayList<>();
        for (int i = 0; i < n; i++) {
            if (adj[i].size() == 1) leaves.add(i);
        }

        int remainingNodes = n;
        while (remainingNodes > 2) {
            remainingNodes -= leaves.size();
            List<Integer> newLeaves = new ArrayList<>();
            for (int leaf : leaves) {
                int neighbor = adj[leaf].iterator().next();
                adj[neighbor].remove(leaf);
                if (adj[neighbor].size() == 1) newLeaves.add(neighbor);
            }
            leaves = newLeaves;
        }

        return leaves;
    }
}

C++:

class Solution {
public:
    vector<int> findMinHeightTrees(int n, vector<vector<int>>& edges) {
        if (n <= 2) {
            vector<int> res;
            for (int i = 0; i < n; i++) res.push_back(i);
            return res;
        }

        vector<unordered_set<int>> adj(n);
        for (auto& e : edges) {
            adj[e[0]].insert(e[1]);
            adj[e[1]].insert(e[0]);
        }

        vector<int> leaves;
        for (int i = 0; i < n; i++) {
            if (adj[i].size() == 1) leaves.push_back(i);
        }

        int remainingNodes = n;
        while (remainingNodes > 2) {
            remainingNodes -= leaves.size();
            vector<int> newLeaves;
            for (int leaf : leaves) {
                int neighbor = *adj[leaf].begin();
                adj[neighbor].erase(leaf);
                if (adj[neighbor].size() == 1) newLeaves.push_back(neighbor);
            }
            leaves = newLeaves;
        }

        return leaves;
    }
};

Go:

func findMinHeightTrees(n int, edges [][]int) []int {
    if n <= 2 {
        res := make([]int, n)
        for i := 0; i < n; i++ { res[i] = i }
        return res
    }

    adj := make([]map[int]bool, n)
    for i := 0; i < n; i++ { adj[i] = make(map[int]bool) }
    for _, e := range edges {
        adj[e[0]][e[1]] = true
        adj[e[1]][e[0]] = true
    }

    leaves := []int{}
    for i := 0; i < n; i++ {
        if len(adj[i]) == 1 { leaves = append(leaves, i) }
    }

    remainingNodes := n
    for remainingNodes > 2 {
        remainingNodes -= len(leaves)
        newLeaves := []int{}
        for _, leaf := range leaves {
            var neighbor int
            for nbr := range adj[leaf] { neighbor = nbr }
            delete(adj[neighbor], leaf)
            if len(adj[neighbor]) == 1 { newLeaves = append(newLeaves, neighbor) }
        }
        leaves = newLeaves
    }

    return leaves
}

Ruby:

def find_min_height_trees(n, edges)
  return (0...n).to_a if n <= 2

  adj = Array.new(n) { Set.new }
  edges.each do |u, v|
    adj[u] << v
    adj[v] << u
  end

  leaves = (0...n).select { |i| adj[i].size == 1 }

  remaining_nodes = n
  while remaining_nodes > 2
    remaining_nodes -= leaves.length
    new_leaves = []
    leaves.each do |leaf|
      neighbor = adj[leaf].first
      adj[neighbor].delete(leaf)
      new_leaves << neighbor if adj[neighbor].size == 1
    end
    leaves = new_leaves
  end

  leaves
end

5. Sequence Reconstruction

LeetCode 444

Brief: Determine if a unique shortest common supersequence org can be reconstructed from a list of sequences.
Why this pattern?: We build a dependency graph and check if its topological order is unique and matches org.
Key Insight: A topological sort is unique if and only if at each step of Kahn’s algorithm, the queue contains exactly one element. Complexity is
O(V + E)
.

  flowchart LR
    1((1)) --> 2((2))
    2((2)) --> 3((3))
    1((1)) --> 3((3))
    style 1 fill:#f9f
    style 2 fill:#f9f
    style 3 fill:#f9f

JavaScript:

function sequenceReconstruction(org, seqs) {
    const adj = new Map();
    const indegree = new Map();
    const nodes = new Set();
    for (const seq of seqs) {
        for (const x of seq) nodes.add(x);
        for (let i = 0; i < seq.length - 1; i++) {
            if (!adj.has(seq[i])) adj.set(seq[i], new Set());
            if (adj.get(seq[i]).add(seq[i+1])) {
                indegree.set(seq[i+1], (indegree.get(seq[i+1]) || 0) + 1);
            }
        }
    }

    if (nodes.size !== org.length) return false;

    const queue = [];
    for (const x of nodes) {
        if (!indegree.get(x)) queue.push(x);
    }

    let index = 0;
    while (queue.length === 1) {
        const u = queue.shift();
        if (u !== org[index++]) return false;
        if (adj.has(u)) {
            for (const v of adj.get(u)) {
                indegree.set(v, indegree.get(v) - 1);
                if (indegree.get(v) === 0) queue.push(v);
            }
        }
    }

    return index === org.length && queue.length === 0;
}

Python:

from collections import deque

def sequenceReconstruction(org, seqs):
    adj = {}
    indegree = {}
    nodes = set()
    for seq in seqs:
        for x in seq:
            nodes.add(x)
            if x not in adj: adj[x] = set()
            if x not in indegree: indegree[x] = 0
        for i in range(len(seq) - 1):
            if seq[i+1] not in adj[seq[i]]:
                adj[seq[i]].add(seq[i+1])
                indegree[seq[i+1]] += 1

    if len(nodes) != len(org): return False

    queue = deque([x for x in nodes if indegree[x] == 0])
    index = 0
    while len(queue) == 1:
        u = queue.popleft()
        if index >= len(org) or u != org[index]: return False
        index += 1
        for v in adj[u]:
            indegree[v] -= 1
            if indegree[v] == 0:
                queue.append(v)

    return index == len(org) and not queue

Java:

class Solution {
    public boolean sequenceReconstruction(int[] org, List<List<Integer>> seqs) {
        Map<Integer, Set<Integer>> adj = new HashMap<>();
        Map<Integer, Integer> indegree = new HashMap<>();
        for (List<Integer> seq : seqs) {
            for (int i = 0; i < seq.size(); i++) {
                adj.putIfAbsent(seq.get(i), new HashSet<>());
                indegree.putIfAbsent(seq.get(i), 0);
                if (i > 0) {
                    if (adj.get(seq.get(i-1)).add(seq.get(i))) {
                        indegree.put(seq.get(i), indegree.get(seq.get(i)) + 1);
                    }
                }
            }
        }

        if (org.length != indegree.size()) return false;

        Queue<Integer> q = new LinkedList<>();
        for (int key : indegree.keySet()) {
            if (indegree.get(key) == 0) q.offer(key);
        }

        int index = 0;
        while (q.size() == 1) {
            int u = q.poll();
            if (org[index++] != u) return false;
            for (int v : adj.get(u)) {
                indegree.put(v, indegree.get(v) - 1);
                if (indegree.get(v) == 0) q.offer(v);
            }
        }

        return index == org.length;
    }
}

C++:

class Solution {
public:
    bool sequenceReconstruction(vector<int>& org, vector<vector<int>>& seqs) {
        unordered_map<int, unordered_set<int>> adj;
        unordered_map<int, int> indegree;
        for (auto& seq : seqs) {
            for (int i = 0; i < seq.size(); i++) {
                if (adj.find(seq[i]) == adj.end()) {
                    adj[seq[i]] = unordered_set<int>();
                    indegree[seq[i]] = 0;
                }
                if (i > 0) {
                    if (adj[seq[i-1]].insert(seq[i]).second) {
                        indegree[seq[i]]++;
                    }
                }
            }
        }

        if (org.size() != indegree.size()) return false;

        queue<int> q;
        for (auto& p : indegree) {
            if (p.second == 0) q.push(p.first);
        }

        int index = 0;
        while (q.size() == 1) {
            int u = q.front(); q.pop();
            if (org[index++] != u) return false;
            for (int v : adj[u]) {
                if (--indegree[v] == 0) q.push(v);
            }
        }

        return index == org.size();
    }
};

Go:

func sequenceReconstruction(org []int, seqs [][]int) bool {
    adj := make(map[int]map[int]bool)
    indegree := make(map[int]int)
    for _, seq := range seqs {
        for i, val := range seq {
            if _, exists := adj[val]; !exists {
                adj[val] = make(map[int]bool)
                indegree[val] = 0
            }
            if i > 0 {
                prev := seq[i-1]
                if !adj[prev][val] {
                    adj[prev][val] = true
                    indegree[val]++
                }
            }
        }
    }

    if len(org) != len(indegree) { return false }

    queue := []int{}
    for k, v := range indegree {
        if v == 0 { queue = append(queue, k) }
    }

    index := 0
    for len(queue) == 1 {
        u := queue[0]
        queue = queue[1:]
        if index >= len(org) || org[index] != u { return false }
        index++
        for v := range adj[u] {
            indegree[v]--
            if indegree[v] == 0 { queue = append(queue, v) }
        }
    }

    return index == len(org)
}

Ruby:

def sequence_reconstruction(org, seqs)
  adj = {}
  indegree = {}
  seqs.each do |seq|
    seq.each_with_index do |val, i|
      adj[val] ||= Set.new
      indegree[val] ||= 0
      if i > 0
        prev = seq[i-1]
        adj[prev] ||= Set.new
        if adj[prev].add?(val)
            indegree[val] += 1
        end
      end
    end
  end

  return false if org.length != indegree.size

  queue = indegree.select { |_, v| v == 0 }.keys
  index = 0
  while queue.length == 1
    u = queue.shift
    return false if org[index] != u
    index += 1
    adj[u].each do |v|
      indegree[v] -= 1
      queue << v if indegree[v] == 0
    end
  end

  index == org.length
end

Recommended Study Order

Course Schedule: Master the basic Kahn’s algorithm for cycle detection.
Course Schedule II: Learn how to capture and return the actual ordering.
Alien Dictionary: Practice building a graph from complex string relationships.
Sequence Reconstruction: Understand the condition for a unique topological sort.
Minimum Height Trees: Apply topological concepts to undirected graphs and level-by-level pruning.