Sort Items by Groups Respecting Dependencies - Solution & Explanation
Problem Statement
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 and it's equal to -1 if the i-th item belongs to no group. The items and the groups are zero indexed. A group can have no item belonging to it.
Return a sorted list of the items such that:
- The items that belong to the same group are next to each other in the sorted list.
- There are some relations between these items where
beforeItems[i]is a list containing all the items that should come before thei-th item in the sorted array (to the left of thei-th item).
Return any solution if there is more than one solution and return an empty list if there is no solution.
Example 1:
Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3,6],[],[],[]] Output: [6,3,4,1,5,2,0,7]
Example 2:
Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]] Output: [] Explanation: This is the same as example 1 except that 4 needs to be before 6 in the sorted list.
Constraints:
1 <= m <= n <= 3 * 104group.length == beforeItems.length == n-1 <= group[i] <= m - 10 <= beforeItems[i].length <= n - 10 <= beforeItems[i][j] <= n - 1i != beforeItems[i][j]beforeItems[i]does not contain duplicates elements.
Approach Overview
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.
Approach 1: Topological Sort with Grouped Items
This approach involves processing the items and grouping them based on dependency relationships. We'll use topological sorting for individual items within a group. The main steps are:
- Assign groups for items with no valid group using temporary group numbers.
- Build graphs for both items and groups based on dependency constraints.
- Perform topological sorting on both item graph and group graph.
This Python solution implements the approach of topological sorting using graph algorithms. We first assign temporary groups to items without any group. Then, two graphs (one for items and another for groups) are built based on given dependencies. We perform topological sorting on item and group graphs to determine the correct order. The results are gathered by reorganizing items according to their group order and finally returning the sorted list. If any of the topological sort fails to return a complete order, we return an empty list.
Complexity
The time complexity of this solution is O(n + m) where n is the number of items and m is the number of groups, due to the topological sort operation. The space complexity is also O(n + m) for storing the adjacency list, indegree count, and result list.
Approach 2: Using Priority Queues for Topological Sorting
This approach incorporates priority queues (heaps) to perform topological sorting on items based on their dependencies, akin to a 'priority' based execution. It works by:
- Identifying independent items (i.e., items with no dependencies) and adding them to a min-heap.
- Processing items from the heap to ensure a strict order while satisfying the dependency conditions through the graph.
The C++ solution utilizes a min-priority queue for managing items with zero dependencies. This ensures items are processed in order of their natural indices, which mimics the behavior of prioritizing certain operations. After identifying initial independent items, it iterates through the graph, managing dependencies and constructing the correct order through traditional topological sorting mechanisms. The heap structure adds an extra layer of determinism by processing the lowest index 'ready' item first.
Complexity
The time complexity remains O(n + m) due to the heap operations and graph traversal. Space complexity is O(n + m) to store necessary elements and dependency structures.
Approach 3: Topological Sorting
First, we traverse the array group. For each project, if it does not belong to any group, we create a new group for it with the ID m, and increment m. This ensures that all projects belong to some group. Then, we use an array groupItems to record the projects contained in each group. The array index is the group ID, and the array value is the list of projects in the group.
Next, we need to build the graph. For each project, we need to build two types of graphs: one for the projects and one for the groups. We traverse the array group. For the current project i, its group is group[i]. We traverse beforeItems[i], and for each project j in it, if group[i] = group[j], it means that i and j belong to the same group. We add an edge j \to i in the project graph. Otherwise, it means that i and j belong to different groups. We add an edge group[j] \to group[i] in the group graph, and update the corresponding in-degree array.
Next, we perform topological sorting on the group graph to get the sorted group list groupOrder. If the length of the sorted list is not equal to the total number of groups, it means that the sorting cannot be completed, so we return an empty list. Otherwise, we traverse groupOrder, and for each group gi, we perform topological sorting on the project list groupItems[gi] to get the sorted project list itemOrder. If the length of the sorted list is not equal to the total number of projects in the group, it means that the sorting cannot be completed, so we return an empty list. Otherwise, we add the projects in itemOrder to the answer array, and finally return this answer array.
The time complexity is O(n + m), and the space complexity is O(n + m). Here, n and m are the total number of projects and groups, respectively.
Code
Python
Java
C++
Go
TypeScript
Complexity Comparison
| Approach | Complexity |
|---|---|
| Topological Sort with Grouped Items | The time complexity of this solution is O(n + m) where n is the number of items and m is the number of groups, due to the topological sort operation. The space complexity is also O(n + m) for storing the adjacency list, indegree count, and result list. |
| Using Priority Queues for Topological Sorting | The time complexity remains O(n + m) due to the heap operations and graph traversal. Space complexity is O(n + m) to store necessary elements and dependency structures. |
| Topological Sorting | — |
Detailed Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Topological Sort with Grouped Items | O(n + m) | O(n + m) | General optimal solution when resolving dependencies across grouped items |
| Priority Queue Based Topological Sort | O((n + m) log n) | O(n + m) | When deterministic or lexicographically ordered valid results are preferred |
Video Solution
Sort Items by Groups Respecting Dependencies | Broken into Simple Steps | Intuition | Leetcode-1203 • codestorywithMIK • 10,952 views views
Watch 9 more video solutions →Frequently Asked Questions
Is Sort Items by Groups Respecting Dependencies easy or hard?
Sort Items by Groups Respecting Dependencies Python/Java solution
How to solve Sort Items by Groups Respecting Dependencies in O(n + m)?
What is the best approach for Sort Items by Groups Respecting Dependencies?
Is Sort Items by Groups Respecting Dependencies asked at Google/Amazon/Meta?
What data structure is used in Sort Items by Groups Respecting Dependencies?
What is the time complexity of Sort Items by Groups Respecting Dependencies?
Ready to solve this problem?
Practice Sort Items by Groups Respecting Dependencies with our built-in code editor and test cases.
Practice on FleetCode