DSA problem
Sort Items by Groups Respecting Dependencies
There are n items each belonging to zero or one of m groups, where group[i] is the group identifier of item i and -1 means the item belongs to no group. The items and the groups are zero-indexed. You are also given a list beforeItems where beforeItems[i] lists items that must appear before item i in the final ordering. Return any solution that satisfies all the following: items in the same group are adjacent in the order, and the item-level "before" constraints are respected. Return an empty array if no such order exists.
The challenge is that ordering operates on two intertwined levels — items inside a group must be contiguous (a group-level order) AND the per-item dependencies cut across groups (an item-level order). The clean way to handle this is two coupled topological sorts.
First, assign every ungrouped item (group[i] == -1) a unique fresh group id so that every item now lives in some group. Next, walk beforeItems once: each dependency b → a either connects items inside the same group (an item-level edge) or connects different groups (a group-level edge groupOf(b) → groupOf(a)). Build two DAGs from these edges, with separate in-degree arrays per level.
Run Kahn's BFS to obtain a topological order of the groups, then run Kahn's BFS over items but seed each group's queue with its own zero-in-degree items, producing a per-group item order. Finally walk the groups in their topo order and emit each group's items in their per-group topo order. If either Kahn's run cannot consume all of its nodes, a cycle existed and the answer is the empty array. Total complexity is O(n + m + dependencies), which is asymptotically optimal.
Examples
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]n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]][]n = 5, m = 1, group = [0,0,0,0,0], beforeItems = [[1],[2],[3],[4],[]][4,3,2,1,0]Constraints
- 1 <= m <= n <= 3 * 10^4
- group.length == beforeItems.length == n
- -1 <= group[i] <= m - 1
- 0 <= beforeItems[i].length <= n - 1
- 0 <= beforeItems[i][j] <= n - 1
- i != beforeItems[i][j].
- beforeItems[i] does not contain duplicates.
3 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.