What is the time complexity of LeetCode 1203. Sort Items by Groups Respecting Dependencies?

The Python solution on this page runs in O(n + m).

What is the space complexity of LeetCode 1203. Sort Items by Groups Respecting Dependencies?

The Python solution on this page uses O(n + m) auxiliary space.

Sort Items by Groups Respecting Dependencies — LeetCode 1203 Python Solution

HardDepth-First SearchBreadth-First SearchGraphTopological Sort

Problem: #1203
Pattern: Topological Sort
Reading time: 8 min
Source: leetcode.com

The problem

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.

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,1,5,2,0,7]

Python solution

Python

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

Complexity

Measure	Complexity
Time	O(n + m)
Space	O(n + m) auxiliary

Pattern: Topological Sort

Order a set of tasks so that every dependency comes before the thing that needs it. LeetCode 1203. Sort Items by Groups Respecting Dependencies is filed here because LeetCode tags it Topological Sort, which is the vocabulary this hub collects.

The topological sort guide has the Python template for the pattern and the 32 LeetCode problems that use it.

Frequently asked questions

How hard is LeetCode 1203. Sort Items by Groups Respecting Dependencies?: LeetCode 1203. Sort Items by Groups Respecting Dependencies is rated Hard on LeetCode.
What is the time complexity of LeetCode 1203. Sort Items by Groups Respecting Dependencies?: The Python solution on this page runs in O(n + m).
What is the space complexity of LeetCode 1203. Sort Items by Groups Respecting Dependencies?: The Python solution on this page uses O(n + m) auxiliary space.
What topics does LeetCode 1203. Sort Items by Groups Respecting Dependencies cover?: LeetCode 1203. Sort Items by Groups Respecting Dependencies is tagged Depth-First Search, Breadth-First Search, Graph and Topological Sort on LeetCode.