LeetCode 1203 Sort Items by Groups Respecting Dependencies - Implementation - Topological Sort | Pattern 22: LeetCode Interview Patterns

##### ###### ##### ### # # ### # # ###### ## ## ## ## ## ## ## # # # # # ## ##### #### ##### # # # # # # # #### ## # ## ## ## ## # # # # # ## ## # ###### ## ### # ### # ######

Two-level topological sort: groups, then items within groups.

function sortItems(n, m, group, beforeItems): for i in range(n): if group[i] == -1: group[i] = m m += 1

groupGraph = [set() for _ in range(m)]
groupInDegree = [0] * m
itemGraph = [set() for _ in range(n)]
itemInDegree = [0] * n

for item in range(n):
    for before in beforeItems[item]:
        itemGraph[before].add(item)
        itemInDegree[item] += 1
        if group[item] != group[before]:
            if group[item] not in groupGraph[group[before]]:
                groupGraph[group[before]].add(group[item])
                groupInDegree[group[item]] += 1

def topoSort(graph, inDegree, nodes):
    queue = [n for n in nodes if inDegree[n] == 0]
    result = []
    while queue:
        node = queue.pop(0)
        result.append(node)
        for neighbor in graph[node]:
            inDegree[neighbor] -= 1
            if inDegree[neighbor] == 0:
                queue.append(neighbor)
    return result if len(result) == len(nodes) else []

groupOrder = topoSort(groupGraph, groupInDegree, range(m))
if not groupOrder:
    return []

groupItems = [[] for _ in range(m)]
for i in range(n):
    groupItems[group[i]].append(i)

result = []
for g in groupOrder:
    sortedItems = topoSort(itemGraph, itemInDegree, groupItems[g])
    if len(sortedItems) != len(groupItems[g]):
        return []
    result.extend(sortedItems)
return result

$O(n + E)$ time and space.