LeetCode Solutions Blog

Sort Items by Groups Respecting Dependencies

Difficulty: Hard

Problem Description

You are given n items each belonging to zero or one of m groups, where group[i] indicates the group of the i-th item, and it's equal to -1 if the item belongs to no group. Additionally, you have a list beforeItems[i] which contains all the items that should come before the i-th item in the sorted array. Your task is to return a sorted list of items such that:

Items that belong to the same group are next to each other.
The order of items respects the given dependencies.

If there is no valid sorting, return an empty list.

Key Insights

The problem can be modeled as a directed graph where each item is a node, and directed edges represent the dependency from beforeItems[i] to i.
We can utilize topological sorting to determine a valid order of items.
Groups can also be treated as nodes, and we may need to perform topological sorting on groups as well to maintain group order.

Space and Time Complexity

Time Complexity: O(n + m) for processing nodes and edges in the graph.
Space Complexity: O(n + m) for storing the adjacency lists and in-degree counts.

Solution

The solution involves the following steps:

Graph Construction: Build a directed graph where each item points to its dependencies based on beforeItems. Additionally, maintain a mapping of items to their respective groups.
Topological Sort for Items: Perform a topological sort on the items to determine a valid order that respects the dependencies.
Group Processing: After obtaining the sorted order of items, group the items based on their group assignments and then perform a topological sort on these groups.
Final Output: Construct the final output by concatenating the sorted items of each group in the order determined by the group topological sort.

Code Solutions

from collections import defaultdict, deque

def sortItems(n, m, group, beforeItems):
    # Step 1: Assign ungrouped items to new groups
    new_group_id = m
    for i in range(n):
        if group[i] == -1:
            group[i] = new_group_id
            new_group_id += 1

    # Step 2: Build the graph for items and groups
    item_graph = defaultdict(list)
    group_graph = defaultdict(list)
    item_in_degree = [0] * n
    group_in_degree = [0] * new_group_id

    for i in range(n):
        for before in beforeItems[i]:
            item_graph[before].append(i)
            item_in_degree[i] += 1
            if group[before] != group[i]:
                group_graph[group[before]].append(group[i])
                group_in_degree[group[i]] += 1

    # Step 3: Topological sort on items
    item_order = []
    item_queue = deque([i for i in range(n) if item_in_degree[i] == 0])

    while item_queue:
        item = item_queue.popleft()
        item_order.append(item)
        for neighbor in item_graph[item]:
            item_in_degree[neighbor] -= 1
            if item_in_degree[neighbor] == 0:
                item_queue.append(neighbor)

    if len(item_order) < n:
        return []

    # Step 4: Topological sort on groups
    group_order = []
    group_queue = deque([g for g in range(new_group_id) if group_in_degree[g] == 0])

    while group_queue:
        g = group_queue.popleft()
        group_order.append(g)
        for neighbor in group_graph[g]:
            group_in_degree[neighbor] -= 1
            if group_in_degree[neighbor] == 0:
                group_queue.append(neighbor)

    if len(group_order) < new_group_id:
        return []

    # Step 5: Produce the final sorted list
    group_to_items = defaultdict(list)
    for item in item_order:
        group_to_items[group[item]].append(item)

    result = []
    for g in group_order:
        result.extend(group_to_items[g])

    return result