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 = [[],[6],[5],[6],[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 = [[],[6],[5],[6],[3],[],[4],[]]
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)
            return topological_order if len(topological_order) == len(graph) else []

        # 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 = [0] * n
        # create graph, indegree map for between groups
        graph_groups = [[] for _ in range(m)]
        indegree_groups = [0] * 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

Leave a reply