Sort Items by Groups Respecting Dependencies
Hard · Graphs · Depth-First Search · Breadth-First Search · Graph · Topological Sort
Problem
There are n items, numbered 0 to n - 1, and m groups, numbered 0 to m - 1. group[i] is the group item i belongs to, or -1 if the item belongs to no group. Groups may be empty.
You are also given beforeItems, where beforeItems[i] lists every item that must appear before item i in the final ordering.
Return an ordering of all n items such that (1) every dependency in beforeItems is respected and (2) all items of the same group sit next to each other. If several orderings work, return any of them; if none exists, return an empty list.
Examples
Input: n = 5, m = 2, group = [0,0,1,-1,1], beforeItems = [[],[3],[0],[],[2]] Output: [3,0,1,2,4]
Item 3 (no group) must come before item 1, and group 0 = {0, 1} must come before group 1 = {2, 4} because item 0 comes before item 2. This answer puts 3 first, then 0 and 1, then 2 and 4.
Input: n = 6, m = 2, group = [0,1,-1,0,1,-1], beforeItems = [[],[0],[],[1],[],[]] Output: []
Item 0 (group 0) comes before item 1 (group 1), which comes before item 3 (group 0 again), so group 0 cannot stay together: the answer is empty.
Input: n = 3, m = 1, group = [-1,-1,-1], beforeItems = [[2],[0],[]] Output: [2,0,1]
Without groups only the dependencies matter: 2 before 0 before 1.
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] has no duplicate entries
Approaches
- Baseline: try every ordering — time O(n! · (n + E)), space O(n)
Follow-up
Two-level ordering problems (tasks inside projects, courses inside modules) all reduce to one topological sort per level, glued together. The use cases ask only whether an arrangement exists, and for the order with the smallest item numbers first when there are no groups. Any valid ordering is accepted: the tests check the two conditions, not one fixed answer.
Related problems
Start free on Cariara · Coding problems · System design studio
