Sort Items by Groups Respecting Dependencies
Hard · Graphs · Explanation and code example
Topological Sort (Kahn's Algorithm)
How it works
Kahn's algorithm offers an iterative approach to topological sorting using in-degrees. Nodes with no incoming edges (in-degree 0) can be processed first. As we process each node, we reduce the in-degree of its neighbors. This BFS-style approach naturally detects cycles: if we cannot process all nodes, a cycle exists.
Steps
- Assign unique group IDs to ungrouped items.
- Build item and group adjacency lists, tracking
indegreefor both. - For the item graph, add an edge from each prerequisite to the dependent item.
- For the group graph, add an edge when a dependency crosses group boundaries.
- Perform Kahn's algorithm on items:
- Start with all items having
indegree0. - Process items, reducing
indegrees of neighbors. - If the result size does not equal
n, return empty (cycle detected).
- Start with all items having
- Perform Kahn's algorithm on groups similarly.
- Group the topologically sorted items by their group ID.
- Output items in group topological order.
Complexity
- Time complexity:
O(V + E) - Space complexity:
O(V + E)
Where
Vis the number of items andEis the total number ofbeforeItemsdependencies.
Things to watch for
Forgetting to Assign Unique Group IDs to Ungrouped Items
Items with group[i] == -1 must each be assigned a unique group ID. A common mistake is to either skip these items or assign them all to the same group. If ungrouped items share a group ID, they will be forced to appear consecutively in the output, which may violate dependency constraints.
Only Performing One Level of Topological Sort
This problem requires two separate topological sorts: one for items within groups and one for the groups themselves. Attempting to solve it with a single topological sort will fail because it cannot properly handle the constraint that items in the same group must appear consecutively.
Ignoring Cross-Group Dependencies When Building the Group Graph
When item A depends on item B and they belong to different groups, B's group must come before A's group. Forgetting to add edges to the group graph for cross-group dependencies will result in incorrect group ordering and wrong answers.
Not Detecting Cycles in Both Graphs
Cycles can exist in either the item graph or the group graph. If a cycle exists in either graph, no valid ordering exists and an empty array should be returned. Failing to check for cycles in both graphs can lead to infinite loops or incorrect outputs.
Incorrect Handling of Empty Groups
After topological sorting, some groups may have no items assigned to them. When iterating through the sorted groups to build the final result, failing to handle empty groups gracefully can cause errors or incorrect output.
Python code example
from collections import defaultdict, deque
class Solution:
def sortItems(self, n, m, group, beforeItems):
for i in range(n):
if group[i] == -1:
group[i] = m
m += 1
item_adj = defaultdict(list)
group_adj = defaultdict(list)
item_indegree = [0] * n
group_indegree = [0] * m
for i in range(n):
for par in beforeItems[i]:
item_adj[par].append(i)
item_indegree[i] += 1
if group[i] != group[par]:
group_adj[group[par]].append(group[i])
group_indegree[group[i]] += 1
itm = self.topo_sort(item_adj, item_indegree, n)
if not itm: return []
grp = self.topo_sort(group_adj, group_indegree, m)
if not grp: return []
grouping = defaultdict(list)
for i in itm:
grouping[group[i]].append(i)
res = []
for g in grp:
res.extend(grouping[g])
return res
def topo_sort(self, adj, indegree, N):
topo = []
q = deque([i for i in range(N) if indegree[i] == 0])
while q:
node = q.popleft()
topo.append(node)
for neighbor in adj[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
q.append(neighbor)
return topo if len(topo) == N else []
C++ code example
class Solution {
public:
vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
for (int i = 0; i < n; i++) {
if (group[i] == -1) group[i] = m++;
}
vector<vector<int>> itemAdj(n), groupAdj(m);
vector<int> itemIndegree(n, 0), groupIndegree(m, 0);
for (int i = 0; i < n; i++) {
for (int& par : beforeItems[i]) {
itemAdj[par].push_back(i);
itemIndegree[i]++;
if (group[i] != group[par]) {
groupAdj[group[par]].push_back(group[i]);
groupIndegree[group[i]]++;
}
}
}
vector<int> itm = topoSort(itemAdj, itemIndegree, n);
if (itm.empty()) return {};
vector<int> grp = topoSort(groupAdj, groupIndegree, m);
if (grp.empty()) return {};
unordered_map<int, vector<int>> grouping;
for (int& i : itm) {
grouping[group[i]].push_back(i);
}
vector<int> res;
for (int& g : grp) {
res.insert(res.end(), grouping[g].begin(), grouping[g].end());
}
return res;
}
private:
vector<int> topoSort(vector<vector<int>>& adj, vector<int>& indegree, int N) {
queue<int> q;
vector<int> topo;
for (int i = 0; i < N; i++) {
if (indegree[i] == 0) q.push(i);
}
while (!q.empty()) {
int node = q.front(); q.pop();
topo.push_back(node);
for (int& neighbor : adj[node]) {
indegree[neighbor]--;
if (indegree[neighbor] == 0) q.push(neighbor);
}
}
return topo.size() == N ? topo : vector<int>();
}
};
Source and license
Adapted from NeetCode’s source · MIT license. Node types are supplied by LeetCode where needed.