Sort Items by Groups Respecting Dependencies
Problem
There are n items, each belonging to a group (group -1 means no group). beforeItems[i] lists items that must come before item i. Return a sorted order of items so that items of the same group are contiguous and all beforeItems constraints are satisfied, or an empty array if impossible. The canonical solution runs a topological sort over the groups and a topological sort of items within each group; both layers use Kahn's algorithm and a cycle means no valid order exists.
n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]][6, 3, 4, 1, 5, 2, 0, 7]The visualization below focuses on the core engine: Kahn's topological sort over a dependency graph. Enter directed edges a→b (a must come before b); the algorithm peels off zero in-degree nodes one at a time. If some nodes never reach in-degree 0, a cycle exists.
from collections import deque
def sort_items(n, m, group, before_items):
# Give every ungrouped item its own group id.
for i in range(n):
if group[i] == -1:
group[i] = m
m += 1
def topo(graph, indeg, nodes):
q = deque([x for x in nodes if indeg[x] == 0])
order = []
while q:
x = q.popleft()
order.append(x)
for y in graph[x]:
indeg[y] -= 1
if indeg[y] == 0:
q.append(y)
return order if len(order) == len(nodes) else []
g_graph = [[] for _ in range(m)]
g_indeg = [0] * m
i_graph = [[] for _ in range(n)]
i_indeg = [0] * n
for i in range(n):
for j in before_items[i]:
if group[i] == group[j]:
i_graph[j].append(i); i_indeg[i] += 1
else:
g_graph[group[j]].append(group[i]); g_indeg[group[i]] += 1
group_order = topo(g_graph, g_indeg, range(m))
if not group_order:
return []
item_order = topo(i_graph, i_indeg, range(n))
if not item_order:
return []
buckets = {gid: [] for gid in group_order}
for x in item_order:
buckets[group[x]].append(x)
res = []
for gid in group_order:
res.extend(buckets[gid])
return resfunction sortItems(n, m, group, beforeItems) {
for (let i = 0; i < n; i++) if (group[i] === -1) group[i] = m++;
function topo(graph, indeg, nodes) {
const q = [];
for (const x of nodes) if (indeg[x] === 0) q.push(x);
const order = [];
while (q.length) {
const x = q.shift();
order.push(x);
for (const y of graph[x]) {
if (--indeg[y] === 0) q.push(y);
}
}
return order.length === nodes.length ? order : [];
}
const gGraph = Array.from({ length: m }, () => []);
const gIndeg = new Array(m).fill(0);
const iGraph = Array.from({ length: n }, () => []);
const iIndeg = new Array(n).fill(0);
for (let i = 0; i < n; i++) {
for (const j of beforeItems[i]) {
if (group[i] === group[j]) { iGraph[j].push(i); iIndeg[i]++; }
else { gGraph[group[j]].push(group[i]); gIndeg[group[i]]++; }
}
}
const gOrder = topo(gGraph, gIndeg, [...Array(m).keys()]);
if (!gOrder.length) return [];
const iOrder = topo(iGraph, iIndeg, [...Array(n).keys()]);
if (!iOrder.length && n) return [];
const buckets = new Map(gOrder.map((g) => [g, []]));
for (const x of iOrder) buckets.get(group[x]).push(x);
const res = [];
for (const g of gOrder) res.push(...buckets.get(g));
return res;
}import java.util.*;
class Solution {
public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
for (int i = 0; i < n; i++) if (group[i] == -1) group[i] = m++;
List<List<Integer>> gGraph = build(m), iGraph = build(n);
int[] gIndeg = new int[m], iIndeg = new int[n];
for (int i = 0; i < n; i++) {
for (int j : beforeItems.get(i)) {
if (group[i] == group[j]) { iGraph.get(j).add(i); iIndeg[i]++; }
else { gGraph.get(group[j]).add(group[i]); gIndeg[group[i]]++; }
}
}
List<Integer> gOrder = topo(gGraph, gIndeg, m);
List<Integer> iOrder = topo(iGraph, iIndeg, n);
if (gOrder.isEmpty() || iOrder.isEmpty()) return new int[0];
Map<Integer, List<Integer>> buckets = new HashMap<>();
for (int g : gOrder) buckets.put(g, new ArrayList<>());
for (int x : iOrder) buckets.get(group[x]).add(x);
int[] res = new int[n]; int k = 0;
for (int g : gOrder) for (int x : buckets.get(g)) res[k++] = x;
return res;
}
private List<List<Integer>> build(int s) {
List<List<Integer>> g = new ArrayList<>();
for (int i = 0; i < s; i++) g.add(new ArrayList<>());
return g;
}
private List<Integer> topo(List<List<Integer>> g, int[] indeg, int cnt) {
Deque<Integer> q = new ArrayDeque<>();
for (int x = 0; x < cnt; x++) if (indeg[x] == 0) q.add(x);
List<Integer> order = new ArrayList<>();
while (!q.isEmpty()) {
int x = q.poll();
order.add(x);
for (int y : g.get(x)) if (--indeg[y] == 0) q.add(y);
}
return order.size() == cnt ? order : new ArrayList<>();
}
}#include <vector>
#include <queue>
using namespace std;
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>> gGraph(m), iGraph(n);
vector<int> gIndeg(m, 0), iIndeg(n, 0);
for (int i = 0; i < n; i++) {
for (int j : beforeItems[i]) {
if (group[i] == group[j]) { iGraph[j].push_back(i); iIndeg[i]++; }
else { gGraph[group[j]].push_back(group[i]); gIndeg[group[i]]++; }
}
}
auto topo = [](vector<vector<int>>& g, vector<int> indeg, int cnt) {
queue<int> q;
for (int x = 0; x < cnt; x++) if (indeg[x] == 0) q.push(x);
vector<int> order;
while (!q.empty()) {
int x = q.front(); q.pop();
order.push_back(x);
for (int y : g[x]) if (--indeg[y] == 0) q.push(y);
}
return (int)order.size() == cnt ? order : vector<int>();
};
vector<int> gOrder = topo(gGraph, gIndeg, m);
vector<int> iOrder = topo(iGraph, iIndeg, n);
if (gOrder.empty() || iOrder.empty()) return {};
vector<vector<int>> buckets(m);
for (int x : iOrder) buckets[group[x]].push_back(x);
vector<int> res;
for (int g : gOrder) for (int x : buckets[g]) res.push_back(x);
return res;
}
};Explanation
This problem has two layers of ordering at once: items inside a group must stay contiguous, and every beforeItems dependency must be respected. The trick is to run a topological sort twice — once on the groups, and once on the items — using Kahn's algorithm.
First, every ungrouped item (group -1) gets its own private group, so each item belongs to exactly one group. Then for each dependency j before i: if they share a group it becomes an item-level edge; if not, it becomes a group-level edge.
Kahn's algorithm repeatedly removes nodes whose in-degree (number of unmet prerequisites) is 0, appending them to the order and decrementing their neighbors. If the produced order doesn't include every node, there is a cycle, so no valid arrangement exists and we return an empty list.
Finally we sort the groups, sort the items, then drop each item into a bucket keyed by its group. Concatenating the buckets in group order keeps each group's items together while honoring all the edges.
The visualization shows the core engine: enter directed edges a→b and watch Kahn's algorithm peel off zero in-degree nodes one by one until the queue empties or a cycle blocks progress.