Research

# [LeetCode 1203] Sort Items by Groups Respecting Dependencies

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 the `i`-th item in the sorted array (to the left of the `i`-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 = [[],,,,[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 = [[],,,,,[],,[]]
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*10^4`
• `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.
```class Solution:

def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:

'''
Two-level topological sort,
one layer for the groups,
another layer for within the groups
'''
# Helper function: returns topological order of a graph, if it exists.
def get_topological_order(graph, indegree):
topological_order = []
# generate a stack with all nodes with 0 indegree, i.e. no prerequisites
stack = [node for node in range(len(graph)) if indegree[node] == 0]
# use a stack for dfs, dfs is used for topological sort
while stack:
vertex = stack.pop()
topological_order.append(vertex)
for neighbor in graph[vertex]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
stack.append(neighbor)

# STEP 1: Create a new group for each item that belongs to no group.
for vertex in range(len(group)):
if group[vertex] == -1:
group[vertex] = m # no-groupers are all placed into their own group
m+=1 # increase the number of groups

# STEP 2: Build directed graphs for items and groups.
'''
List Comprehension
n = 3
graph_items = [[] for _ in range(n)]
print(graph_items) -> [[], [], []]
'''
# create graph, indegree map for within groups
graph_items = [[] for _ in range(n)]
indegree_items =  * n
# create graph, indegree map for between groups
graph_groups = [[] for _ in range(m)]
indegree_groups =  * m

for vertex in range(n):
for dependency in beforeItems[vertex]:
# convert dependencies into neighbors, indegree
# build neighbors for dependency
graph_items[dependency].append(vertex)
# build indegree for vertex
indegree_items[vertex] += 1

if group[vertex] != group[dependency]:
graph_groups[group[dependency]].append(group[vertex])
indegree_groups[group[vertex]] += 1

# STEP 3: Find topological orders of items and groups.
item_order = get_topological_order(graph_items, indegree_items)
group_order = get_topological_order(graph_groups, indegree_groups)
if not item_order or not group_order: return []

# STEP 4: Find order of items within each group.
order_within_group = collections.defaultdict(list) # defaultdict(<class 'list'>, {})
for vertex in item_order:
order_within_group[group[vertex]].append(vertex)

# STEP 5. Combine ordered groups.
res = []
for group in group_order:
res += order_within_group[group]
return res```
Previous Post

Next article