Sort Items by Groups Respecting Dependencies

Explanation & Solution

Description

There are n items each belonging to zero or one of m groups, where group[i] is the group that the i-th item belongs to. Items that do not belong to any group are assigned group[i] = -1. Items with -1 should each be treated as their own unique group.

You are given a 2D array beforeItems, where beforeItems[i] is a list of all items that must come before the i-th item in the sorted order.

Return any valid ordering of the items such that:

1. Items in the same group are adjacent to each other in the result.

2. All dependency constraints from beforeItems are satisfied.

If no valid solution exists, return an empty array.

Input:n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]

-1

Output:[6,3,4,1,5,2,0,7]

Explanation: Items 3, 4, 6 are in group 0. Items 2, 5 are in group 1. Items 0, 1, 7 each form their own group. The output respects all dependency constraints: item 6 comes before items 1, 3, and 4; item 5 comes before item 2; item 3 comes before item 4; and item 6 comes before item 3.

Constraints

1 <= m <= n <= 30000
group.length == n
-1 <= group[i] <= m - 1
beforeItems.length == n
0 <= beforeItems[i].length <= n - 1
0 <= beforeItems[i][j] <= n - 1
i !== beforeItems[i][j]
beforeItems[i] does not contain duplicates

Approach

Topological Sort pattern

1. Assign Unique Groups to Ungrouped Items

Items with group[i] === -1 don't belong to any group
Assign each one a unique new group ID starting from m
This simplifies the algorithm — every item now belongs to exactly one group

2. Build Two Graphs: Item-Level and Group-Level

Item graph: For each dependency prev -> i, add a directed edge from prev to i
Group graph: If prev and i are in different groups, add a directed edge from group[prev] to group[i] (deduplicated with a Set)
Track in-degrees for both graphs

3. Topological Sort of Groups

Use Kahn's algorithm (BFS-based topological sort) on the group graph
This determines the order in which groups should appear
If a cycle is detected (not all groups are sorted), return []

4. Topological Sort of Items Within Each Group

For each group, topologically sort only the items belonging to that group
Use the same item-level graph but restricted to items in the current group
If any group has a cycle among its items, return []

5. Assemble Final Result

Iterate through groups in the topologically sorted group order
For each group, append its items in their sorted order
The result satisfies both constraints: adjacency and dependencies

Key Insight

This problem requires double topological sort — one at the group level and one at the item level within each group
Assigning unique group IDs to ungrouped items avoids special-casing them throughout the algorithm
The group graph captures inter-group dependencies while the item graph captures intra-group ordering

Time

O(n + m + E) where E is the total number of edges across both graphs

Space

O(n + m + E) for storing both graphs

Solution Code

Loud and Rich

Find Eventual Safe States