#1203

Hard

auto_awesomeGraph indegree plus topological ordering

LeetCode Problem Workspace

Sort Items by Groups Respecting Dependencies

Sort items into groups while respecting dependencies using graph indegree tracking and topological ordering patterns effectively.

depth first search breadth first search graph topological sort

Problem Statement

You are given n items each possibly belonging to one of m groups, where group[i] is the group index for item i or -1 if it has no group. Items have dependencies defined in beforeItems, where beforeItems[i] contains all items that must come before item i in the final sorted list.

Return a list of all items sorted so that each item's dependencies are satisfied and items in groups maintain relative ordering. If multiple valid solutions exist, return any of them; return an empty list if no solution exists due to cyclic dependencies.

Examples

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 details omitted.

Example 2

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

Output: []

This is the same as example 1 except that 4 needs to be before 6 in the sorted list.

Constraints

1 <= m <= n <= 3 * 104
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] does not contain duplicates elements.

Solution Approach

Assign Unique Groups to Ungrouped Items

Start by giving each item with group[i] == -1 a unique temporary group index so that all items belong to some group. This simplifies group-level dependency resolution and allows a consistent topological sort.

Build Item and Group Dependency Graphs

Construct two graphs: one at the item level for direct beforeItems dependencies and one at the group level where edges represent any cross-group dependency. Compute indegrees for both graphs to track which items or groups can be processed next.

Topological Sort with Cycle Detection

Perform topological sorting first on groups and then on items within each group using DFS or BFS based on indegree counts. Detect cycles by checking for nodes with remaining indegree at the end; if found, return an empty list as no valid ordering exists.

Complexity Analysis

Metric	Value
Time	Depends on the final approach
Space	Depends on the final approach

Time complexity is O(n + m + total dependencies) because we traverse each node and edge in both item and group graphs once. Space complexity is O(n + m + total dependencies) to store adjacency lists, indegrees, and temporary ordering arrays.

What Interviewers Usually Probe

Candidate identifies the need for dual-level topological sorting.
Candidate correctly assigns unique groups to ungrouped items to prevent cross-group ambiguity.
Candidate accounts for cycles in item or group dependencies.

Common Pitfalls or Variants

Common pitfalls

Failing to assign unique group IDs to items with group[i] == -1 causing invalid cross-group sorting.
Mishandling cycles in dependencies, leading to incorrect output instead of an empty list.
Processing items before group-level dependencies are resolved, breaking the relative ordering pattern.

Follow-up variants

Allowing items to belong to multiple groups and handling overlapping dependencies.
Changing the problem to return the lexicographically smallest valid ordering instead of any valid ordering.
Introducing weighted dependencies where some items must precede others based on priority instead of just presence.

FAQ

What pattern does this problem follow?

This problem follows the graph indegree plus topological ordering pattern, applied to both items and groups with dependency constraints.

How do I handle items without groups?

Assign a unique temporary group ID to each ungrouped item to ensure all items are included in the group-level topological sort.

What if there is no valid ordering?

Detect cycles in the item or group dependency graphs; if a cycle exists, return an empty list as no valid solution is possible.

Can multiple valid outputs exist?

Yes, multiple topological orderings may satisfy all dependencies; any valid ordering can be returned according to the problem requirements.

How do DFS and BFS apply here?

DFS can be used to detect cycles and produce a topological sort recursively, while BFS with indegree tracking produces a valid ordering iteratively for both items and groups.

terminal

Solution

Solution 1: 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.

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

18

19

20

21

22

23

24

25

26

27

28

29

30

31

32

33

34

35

36

37

38

39

40

41

42

43

44

45

46

47

48

49

class Solution:
    def sortItems(
        self, n: int, m: int, group: List[int], beforeItems: List[List[int]]
    ) -> List[int]:
        def topo_sort(degree, graph, items):
            q = deque(i for _, i in enumerate(items) if degree[i] == 0)
            res = []
            while q:
                i = q.popleft()
                res.append(i)
                for j in graph[i]:
                    degree[j] -= 1
                    if degree[j] == 0:
                        q.append(j)
            return res if len(res) == len(items) else []

        idx = m
        group_items = [[] for _ in range(n + m)]
        for i, g in enumerate(group):
            if g == -1:
                group[i] = idx
                idx += 1
            group_items[group[i]].append(i)

        item_degree = [0] * n
        group_degree = [0] * (n + m)
        item_graph = [[] for _ in range(n)]
        group_graph = [[] for _ in range(n + m)]
        for i, gi in enumerate(group):
            for j in beforeItems[i]:
                gj = group[j]
                if gi == gj:
                    item_degree[i] += 1
                    item_graph[j].append(i)
                else:
                    group_degree[gi] += 1
                    group_graph[gj].append(gi)

        group_order = topo_sort(group_degree, group_graph, range(n + m))
        if not group_order:
            return []
        ans = []
        for gi in group_order:
            items = group_items[gi]
            item_order = topo_sort(item_degree, item_graph, items)
            if len(items) != len(item_order):
                return []
            ans.extend(item_order)
        return ans

Continue Practicing

#1462 course schedule iv #802 find eventual safe states #329 longest increasing path in a matrix