Sort Items By Groups Respecting Dependencies - Leetcode Solution

Problem Statement:

You are given a list of items and a list of dependencies where each dependency is represented by a pair [item_i, item_j] meaning item_i depends on item_j. You want to sort the items in such a way that each item appears before all items it depends on.

Return any valid order of the items.

Solution:

The problem requires us to sort the items in such a way that each item appears before all items it depends on. The dependencies are provided in a list of pairs, where the first item in the pair depends on the second item. In order to solve the problem, we can make use of a topological sort.

We first construct a graph using the given dependencies as edges between the vertices. We can then use Kahn's algorithm for topological sorting of the graph.

Kahn's algorithm for topological sorting involves the following steps:

1. Compute the in-degree of each vertex in the graph. In-degree of a vertex represents the number of edges that are directed towards the vertex.

2. Initialize a queue with all vertices in the graph with in-degree 0. These vertices are the ones that have no incoming edges.

3. While the queue is not empty, remove a vertex from the queue, add it to the result list and decrement the in-degree of all its neighbors.

4. If any of the neighbors of the vertex have in-degree 0 after step 3, add them to the queue.

5. Repeat steps 3 and 4 until the queue is empty.

The resulting list would be a valid ordering of the items that respects the dependencies in the original list.

Let's implement the solution in code:

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        # Construct graph for items and group
        group_items = [[] for _ in range(max(group)+1)]
        group_graph = [[] for _ in range(max(group)+1)]
        for i in range(n):
            if group[i] == -1:
                group[i] = m
                m += 1
            group_items[group[i]].append(i)
        item_graph = [[] for _ in range(n)]
        in_degrees = [0 for _ in range(n)]
        for i in range(n):
            for j in beforeItems[i]:
                if group[i] != group[j]:
                    group_graph[group[j]].append(group[i])
                else:
                    item_graph[j].append(i)
                    in_degrees[i] += 1

        # Kahn's algorithm for group and item sorting
        queue = deque()
        result = []
        for i in range(m):
            if not group_graph[i]:
                queue.append(i)
        while queue:
            curr = queue.popleft()
            result += group_items[curr]
            for neighbor in group_graph[curr]:
                in_degrees[neighbor] -= 1
                if in_degrees[neighbor] == 0:
                    queue.append(neighbor)

        for i in result:
            if in_degrees[i] != 0:
                return []

        queue = deque(result)
        item_order = []
        while queue:
            curr = queue.popleft()
            item_order.append(curr)
            for neighbor in item_graph[curr]:
                in_degrees[neighbor] -= 1
                if in_degrees[neighbor] == 0:
                    queue.append(neighbor)

        for i in in_degrees:
            if i != 0:
                return []

        return item_order

Time Complexity: O(n + m + len(beforeItems))

• We first construct the group and item graph, which takes O(n + len(beforeItems))
• We then perform topological sorting on both graphs using Kahn's algorithm, which takes O(n + m)
• Finally, we check if all vertices have an in-degree of 0, which takes O(n)

Space Complexity: O(n + m + len(beforeItems))

• We use adjacency lists to represent the group and item graphs, which takes O(n + m + len(beforeItems))
• We use two queues, one for group and one for item sorting, which can hold up to n elements in total.

1