Sort Items by Groups Respecting Dependencies - Video Solutions

Problem Overview: You are given n items where some belong to groups. Certain items depend on others and must appear later in the ordering. The goal is to return a valid ordering where item dependencies are respected and items from the same group appear together.

Approach 1: Topological Sort with Grouped Items (O(n + m) time, O(n + m) space)

This problem is essentially a dependency graph with an extra constraint: items should be ordered within groups, and groups themselves may depend on other groups. The clean solution builds two graphs. First, assign unique group IDs to items that initially have no group. Then construct a group-level dependency graph and an item-level dependency graph. Run topological sort on groups first, and within each group run another topological sort for its items. By separating group ordering from item ordering, you enforce both dependency rules without mixing constraints. This approach relies heavily on topological sort and general graph traversal techniques.

The key insight: item dependencies sometimes imply group dependencies. When item a depends on item b and they belong to different groups, create an edge between those groups. Once group order is resolved, items inside each group can be sorted independently using the same dependency edges.

Approach 2: Using Priority Queues for Topological Sorting (O((n + m) log n) time, O(n + m) space)

This variation still models the problem as two dependency graphs but uses a priority queue while performing topological sorting. Instead of processing nodes in arbitrary order, nodes with zero in-degree are pushed into a min-heap. This guarantees deterministic ordering when multiple valid nodes are available. The technique works with either breadth-first search style Kahn's algorithm or a modified queue-based traversal. The tradeoff is additional log n cost due to heap operations.

The heap-based approach is useful when deterministic output order is preferred or when platforms require lexicographically smaller valid sequences. Otherwise, the standard queue-based topological sort is faster and simpler.

Recommended for interviews: The grouped topological sort solution is what most interviewers expect. It demonstrates strong graph modeling skills: recognizing two dependency layers and solving them separately. Building both graphs and running Kahn's algorithm in O(n + m) shows you understand dependency resolution and scalable graph traversal.