← DSA Atlas
Dedicated problem page · #1203

Sort Items by Groups Respecting Dependencies

HardTopological SortTwo-level topological sort (order groups, then items within groups)Nested topological sort (Kahn's BFS on item graph and group graph)
Solve on LeetCode ↗
1203
HardTopological SortNested topological sort (Kahn's BFS on item graph and group graph)Two-level topological sort (order groups, then items within groups)

Sort Items by Groups Respecting Dependencies

There are n items belonging to zero or one of m groups (group[i] == -1 means no group). Given beforeItems[i], the items that must come before item i, return any arrangement of items such that (1) items in the same group are contiguous and (2) all beforeItems dependencies are respected. Return an empty list if no valid arrangement exists.

Open official problem prompt ↗
In plain English

Produce a single linear order of items that honors both the per-item precedence rules and the requirement that same-group items form a contiguous block.

Picture it like this

Scheduling conference talks: sessions (groups) must run back-to-back in a sensible order, and within each session the talks have their own prerequisite ordering.

Example
Input
n = 8, m = 2, group = [-1, -1, 1, 0, 0, 1, 0, -1], beforeItems = [[], [6], [5], [6], [3, 6], [], [], []]
Output
[6, 3, 4, 5, 2, 0, 7, 1]
Why
Every dependency is respected and each group's items are consecutive: group 0 = {6,3,4}, group 1 = {5,2}, and the singletons follow.
Constraints
1 <= m <= n <= 3 * 10^4group.length == beforeItems.length == n-1 <= group[i] <= m - 10 <= beforeItems[i].length <= n - 10 <= beforeItems[i][j] <= n - 1beforeItems[i] does not contain i and has no duplicates
Pattern lesson

See the pattern, then code

Two-level topological sort (order groups, then items within groups)
Recognition clue

Ordering constraints exist at two levels (between items and between whole groups, which must stay contiguous), which signals a nested topological sort rather than a single one.

↗
Topological Sort

Prerequisites, dependencies, build order, or scheduling over a DAG.. Treat each ungrouped item as its own private group so every item has a group. Then topologically sort the groups against each other, and independently sort items within each group; concatenating the within-group orders in group order satisfies both contiguity and dependencies.

New words, made simpleKnow these before the algorithm
Grouped item
An item's block assignment; -1 items are promoted to unique singleton groups.
Cross-group edge
A dependency whose endpoints are in different groups, which induces an ordering between those groups.
Nested topological sort
One topological sort at the group level and one at the item level, combined.
Approaches from first idea to best ideaCompare the trade-offs
ApproachHow it thinksCost
Single flat topological sort

Fails contiguity: dependencies can interleave items from different groups.

Sort all items ignoring groups, then hope same-group items land together.

Time O(n + E)Space O(n + E)
Best choiceTwo-level topological sort

Satisfies both constraints and detects cycles at either level.

Order groups by cross-group edges and items by item edges, then concatenate item buckets in group order.

Time O(n + m + E)Space O(n + m + E)
The rule we keep true

Invariant

Within any group, items appear in an order consistent with all intra-group dependencies, and groups appear in an order consistent with all cross-group dependencies, so concatenation preserves every constraint.

Why this is correct

Reasoning

Promoting -1 items to singleton groups means contiguity is automatic for them and blocks are well defined for the rest. Item dependencies that stay inside a group are handled by the item sort within that block; dependencies that cross groups are also enforced by the group sort, which places the whole earlier block before the later one. If any cycle exists at either level, that level's sort returns short and we output [].

The algorithm in three movesSay these aloud before coding
1Assign each -1 item a fresh unique group id so every item is grouped

item order = [0,5,6,7,2,1,3,4]

2Build an item dependency graph and a group dependency graph (adding a group edge only when a dependency crosses group boundaries)

group order = [0,1,2,4,3]

3Topologically sort items and groups separately; if either has a cycle return []

concat -> [6,3,4,5,2,0,7,1]

4Bucket items by group in item-topological order, then emit buckets in group-topological order

Visual trace

Follow the data, one decision at a time

Input snapshotHighlighted cells are involved in this example
g0:{6,3,4}0
g1:{5,2}1
g?:02
g?:13
g?:74
1 · Readgroup with -1 at 0,1,7
2 · AskGive private groups?
3 · Update stategroup = [2,3,1,0,0,1,0,4], m = 5
4 · ResultEvery item now has a group.
Key takeaway

Groups are ordered first, then each group's items are placed contiguously in their own topological order.

Code walkthrough

Read the solution in small chunks

Python 3

Do not memorize the whole program. Connect each group of lines to one job in the algorithm.

  1. 1
    Lines 3-7Promote ungrouped items

    Each -1 becomes its own group so contiguity is trivially satisfied and every item has a home.

  2. 2
    Lines 8-19Build both graphs

    Item edges always; a group edge is added only when a dependency crosses group boundaries.

  3. 3
    Lines 21-33Reusable Kahn's helper

    Returns a full topological order or [] if a cycle leaves nodes unprocessed.

  4. 4
    Lines 35-38Cycle guard

    A cycle at either level makes the whole arrangement impossible.

  5. 5
    Lines 39-45Bucket then concatenate

    Placing item-ordered members into group buckets and emitting buckets in group order yields a valid contiguous layout.

Make it stick

Edge cases, mistakes, and one self-check

E

Edge cases to test

  • All items ungrouped (group all -1) -> reduces to a single item topological sort
  • A cycle among items -> return []
  • A cycle among groups (cross-group dependencies loop) -> return []
  • Items with no dependencies at all -> any order per group works
!

Common beginner mistakes

  • Adding a group self-loop edge when prev and cur share a group, which fabricates a false group cycle
  • Forgetting to promote -1 items, so ungrouped items get lumped together and violate dependencies or contiguity
  • Sorting items and groups but concatenating in item order rather than bucketed group order
  • Not checking both topological sorts for completeness before assembling the result
Check your understanding

Why does giving each ungrouped item its own unique group id keep the algorithm correct?

More in Topological Sort

#207Course ScheduleCycle detection by peeling zero in-degree nodes#210Course Schedule IIEmit nodes in dependency-safe order#269Alien DictionaryDerive edges from adjacent-item comparisons, then topologically sort#310Minimum Height TreesTrim leaves inward until the center remains#329Longest Increasing Path in a MatrixLongest path in an implicit DAG via memoized DFS#2050Parallel Courses IIITopological longest path (critical path)