LeetCode Solutions Blog

Sort Items by Groups Respecting Dependencies

Number: 1309

Difficulty: Hard

Paid? No

Problem Description

Given n items, each belonging to zero or one of m groups (with unassigned items marked as -1), and dependencies specified such that beforeItems[i] lists all items that must come before item i, return a sorted list of the items. The sorted order must ensure that items belonging to the same group appear consecutively and that all dependency relations are satisfied. If no valid ordering exists, return an empty list.

Key Insights

Items belonging to no group (group[i] == -1) should be assigned unique group ids.
Build two graphs: one for items (to handle intra-group ordering) and one for groups (to handle inter-group ordering).
For every dependency (j -> i): if items j and i belong to the same group, add an edge in the item graph; if they belong to different groups, add an edge in the group graph.
Use topological sort (Kahn’s algorithm or DFS based) to determine a valid order for both groups and items.
Combine the ordered items as per the sorted order of groups to get the final answer.

Space and Time Complexity

Time Complexity: O(n + E) where n is the number of items and E is the total number of dependency edges.
Space Complexity: O(n + E) for storing graphs, indegree arrays, and auxiliary data structures.

Solution

We first reassign group ids for ungrouped items (group[i] == -1) to ensure every item is assigned a group. Then, we build two graphs:

A graph for items, connecting nodes within the same group using dependency constraints.
A graph for groups, connecting different groups based on dependency relations across items.

Using topological sort, we obtain an ordering of groups. Then, for each group, we topologically sort the items in that group. Finally, we concatenate the sorted items in the order given by the group sort.
If any cycle is detected (either at the group level or within any group), the function returns an empty list.

Code Solutions

# Python solution for "Sort Items by Groups Respecting Dependencies"

from collections import defaultdict, deque

def sortItems(n, m, group, beforeItems):
    # Step 1: Reassign group ids for ungrouped items (-1) starting from m
    new_group = m
    for i in range(n):
        if group[i] == -1:
            group[i] = new_group
            new_group += 1

    total_groups = new_group

    # Graphs and indegree arrays for groups and items
    group_graph = defaultdict(list)
    group_indegree = [0] * total_groups
    item_graph = defaultdict(list)
    item_indegree = [0] * n

    # Mapping from group id to items in that group
    group_to_items = defaultdict(list)
    for i in range(n):
        group_to_items[group[i]].append(i)

    # Build graphs for items and groups based on dependencies
    for i in range(n):
        for prev in beforeItems[i]:
            # if dependency is within the same group, link in item graph
            if group[prev] == group[i]:
                item_graph[prev].append(i)
                item_indegree[i] += 1
            else:
                # dependency across groups: add edge from group[prev] to group[i]
                group_graph[group[prev]].append(group[i])
                group_indegree[group[i]] += 1
                # Also build the item graph for dependency within items across groups
                item_graph[prev].append(i)
                item_indegree[i] += 1

    # Helper: topological sort function
    def topologicalSort(nodes, graph, indegree):
        order = []
        dq = deque([node for node in nodes if indegree[node] == 0])
        while dq:
            node = dq.popleft()
            order.append(node)
            for neighbor in graph[node]:
                indegree[neighbor] -= 1
                if indegree[neighbor] == 0:
                    dq.append(neighbor)
        if len(order) == len(nodes):
            return order
        else:
            return []   # cycle detected

    # Topologically sort groups
    groups = list(range(total_groups))
    sorted_groups = topologicalSort(groups, group_graph, group_indegree[:])
    if not sorted_groups:
        return []   # return empty list if cycle in groups detected

    # Topologically sort items
    items = list(range(n))
    sorted_items = topologicalSort(items, item_graph, item_indegree[:])
    if not sorted_items:
        return []  # return empty list if cycle in items detected

    # Map each item to its order in the sorted_items list
    item_order = {item: i for i, item in enumerate(sorted_items)}

    # For each group, sort items according to the global item order
    for grp in group_to_items:
        group_to_items[grp].sort(key=lambda x: item_order[x])

    # Build final result following the order of groups from sorted_groups
    result = []
    for grp in sorted_groups:
        result.extend(group_to_items[grp])
    return result

# Example usage:
if __name__ == "__main__":
    n = 8
    m = 2
    group = [-1,-1,1,0,0,1,0,-1]
    beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]
    print(sortItems(n, m, group, beforeItems))