# Sort Items by Groups Respecting Dependencies
**Difficulty:** HARD
[External](https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies)
Canonical: https://scaleengineer.com/dsa/problems/sort-items-by-groups-respecting-dependencies
**Algorithms:** [Depth-First Search](https://scaleengineer.com/algorithms/depth-first-search), [Breadth-First Search](https://scaleengineer.com/algorithms/breadth-first-search), [Topological Sort](https://scaleengineer.com/algorithms/topological-sort)
**Data structures:** Graph
**Companies:** [Citadel](https://scaleengineer.com/companies/citadel)
---
## 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. 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:**

**![](https://assets.glich.co/dsa/sort-items-by-groups-respecting-dependencies/image0.png)**

**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 * 104`
* `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.

# Approaches
## Iterative Search and Placement
This approach attempts to build the sorted list incrementally. In each step, it searches for an item that can be placed next in the sequence, meaning all its direct dependencies have already been placed. It also has to manage the group adjacency constraint simultaneously, which makes the search process complex and inefficient.
**Time:** O(n * (n + k)) or worse. In each of the `n` steps to place an item, we might scan all `n` items to find a valid one. Checking validity involves looking at its dependencies. This makes the approach too slow for the given constraints. · **Space:** O(n + k), where `n` is the number of items and `k` is the total number of dependencies. This is for storing in-degrees and the `beforeItems` list.
**Pros:** Conceptually simple at a high level: find the next valid item and place it.; Avoids the need to explicitly construct graph data structures, potentially saving some space if the dependency graph is sparse.
**Cons:** Highly inefficient due to the repeated scanning for placeable items, leading to a poor time complexity (e.g., O(n^2 + k)).; Handling the group adjacency constraint and group-level dependencies within the main loop is very complex and error-prone.; Detecting cycles, especially group-level cycles, is not straightforward and adds to the complexity.
### Explanation
The fundamental idea is to simulate the sorting process one item at a time. We maintain a count of remaining prerequisites (in-degree) for each item. An item becomes 'placeable' once its in-degree drops to zero. The algorithm repeatedly scans all items to find a placeable one that also fits the grouping rule (items of the same group must be contiguous). When we place an item, we update the in-degree of all other items that depend on it. This method avoids building explicit graphs but pays a heavy price in performance because of the repeated searches and complex state management needed to enforce the grouping constraints on the fly.
### Algorithm
1. **Initialization**: Calculate the in-degree for every item. The in-degree of an item is the number of items that must come before it. Initialize an empty list for the result and a set to track placed items.
2. **Iterative Placement**: Loop until all items have been placed in the result list.
3. **Find Placeable Item**: In each iteration, scan through all `n` items to find an item `i` that meets the following criteria:
    a. It has not been placed yet.
    b. Its in-degree is 0 (all its prerequisites have been placed).
    c. It satisfies the group adjacency constraint. This is the most complex part. We need to track the `current_group` being filled. Item `i` must either belong to `current_group`, or `current_group` must be complete, and placing `i` starts a new group that doesn't violate any group-level dependencies.
4. **Handle Failure**: If no such item `i` can be found in an iteration, it implies a cycle or an impossible ordering. Return an empty list.
5. **Place Item**: Add the found item `i` to the result list and the set of placed items.
6. **Update Dependencies**: For every item `j` that has `i` as a prerequisite, decrement its in-degree since one of its dependencies is now satisfied.
7. **Return Result**: Once the loop completes (all `n` items are placed), return the result list.

## Two-Level Topological Sort
This is the standard and efficient approach for this kind of problem. It correctly models the problem as two separate but related sorting tasks: one for ordering the groups and one for ordering the items within each group. By separating the concerns, we can use a standard topological sort algorithm (like Kahn's algorithm) for each level, leading to an efficient and correct solution.
**Time:** O(n + m + k), where `n` is the number of items, `m` is the initial number of groups, and `k` is the total number of dependencies. This is because building the graphs and running topological sort on them are all linear-time operations. · **Space:** O(n + m + k), to store the two graphs, in-degree arrays, and other auxiliary data structures.
**Pros:** Highly efficient, with a time complexity linear in the size of the input.; Robustly handles all constraints by cleanly separating item-level and group-level dependencies.; Correctly detects both item-level and group-level cycles, which would make a solution impossible.
**Cons:** Requires a good understanding of graph theory and topological sort.; Implementation is more involved than a naive approach due to the need to manage two separate graphs and sorting processes.
### Explanation
The core insight is to deconstruct the problem's constraints into two levels. Intra-group dependencies (`item A` before `item B`, both in `group X`) dictate the ordering inside `group X`. Inter-group dependencies (`item A` in `group X` before `item C` in `group Y`) dictate the ordering of the groups themselves (`group X` before `group Y`).

This leads to a two-level topological sort algorithm. First, we build a graph of groups and topologically sort it to get the correct sequence of groups. Second, we build a graph of items (only considering dependencies between items in the same group) and sort that to get the internal ordering for each group. If either sort fails due to a cycle, no solution exists. Finally, we merge the results: we iterate through the sorted list of groups and, for each group, append its internally sorted items to our final result.

```java
class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        // Step 1: Assign groups to items with no group.
        int nextGroupId = m;
        for (int i = 0; i < n; i++) {
            if (group[i] == -1) {
                group[i] = nextGroupId++;
            }
        }

        // Step 2: Build item and group dependency graphs.
        List<Integer>[] itemGraph = new ArrayList[n];
        int[] itemIndegree = new int[n];
        List<Integer>[] groupGraph = new ArrayList[nextGroupId];
        int[] groupIndegree = new int[nextGroupId];

        for (int i = 0; i < n; i++) {
            itemGraph[i] = new ArrayList<>();
        }
        for (int i = 0; i < nextGroupId; i++) {
            groupGraph[i] = new ArrayList<>();
        }

        for (int i = 0; i < n; i++) {
            for (int prev : beforeItems.get(i)) {
                // Add item dependency
                itemGraph[prev].add(i);
                itemIndegree[i]++;
                
                // If groups are different, add group dependency
                if (group[prev] != group[i]) {
                    groupGraph[group[prev]].add(group[i]);
                    groupIndegree[group[i]]++;
                }
            }
        }

        // Step 3: Topologically sort items and groups.
        List<Integer> sortedItems = topologicalSort(itemGraph, itemIndegree);
        List<Integer> sortedGroups = topologicalSort(groupGraph, groupIndegree);

        if (sortedItems.isEmpty() || sortedGroups.isEmpty()) {
            return new int[0];
        }

        // Step 4: Combine results.
        Map<Integer, List<Integer>> groupToItemsMap = new HashMap<>();
        for (int item : sortedItems) {
            groupToItemsMap.computeIfAbsent(group[item], k -> new ArrayList<>()).add(item);
        }

        int[] result = new int[n];
        int index = 0;
        for (int groupId : sortedGroups) {
            List<Integer> itemsInGroup = groupToItemsMap.getOrDefault(groupId, new ArrayList<>());
            for (int item : itemsInGroup) {
                result[index++] = item;
            }
        }

        return result;
    }

    private List<Integer> topologicalSort(List<Integer>[] graph, int[] indegree) {
        List<Integer> sortedList = new ArrayList<>();
        Queue<Integer> queue = new LinkedList<>();
        for (int i = 0; i < indegree.length; i++) {
            if (indegree[i] == 0) {
                queue.offer(i);
            }
        }

        while (!queue.isEmpty()) {
            int u = queue.poll();
            sortedList.add(u);
            if (graph[u] != null) {
                for (int v : graph[u]) {
                    indegree[v]--;
                    if (indegree[v] == 0) {
                        queue.offer(v);
                    }
                }
            }
        }

        return sortedList.size() == indegree.length ? sortedList : new ArrayList<>();
    }
}
```
### Algorithm
1. **Pre-processing**: Assign new, unique group IDs to all items that initially belong to no group (`group[i] == -1`). This ensures every item has a group, simplifying the logic.
2. **Graph Construction**: Build two separate directed graphs:
    - `itemGraph` and `itemIndegree`: For intra-group dependencies. For each dependency `p -> i` where `group[p] == group[i]`, add an edge to `itemGraph` and increment `itemIndegree[i]`.
    - `groupGraph` and `groupIndegree`: For inter-group dependencies. For each dependency `p -> i` where `group[p] != group[i]`, add an edge `group[p] -> group[i]` to `groupGraph` and increment `groupIndegree[group[i]]`.
3. **Topological Sort of Groups**: Run a topological sort (e.g., Kahn's algorithm) on the `groupGraph`. This determines the required order of the groups themselves. If the sort doesn't include all groups, a cycle exists, and no solution is possible. Return an empty list.
4. **Topological Sort of Items**: Run a topological sort on the `itemGraph`. This determines the relative order of items *within* each group. If this sort fails, an intra-group cycle exists. Return an empty list.
5. **Combine Results**: 
    a. Use a map to store the sorted items from step 4, partitioned by their group ID.
    b. Create the final result list by iterating through the sorted group order from step 3. For each group, append its list of sorted items from the map.
6. **Return Final List**: The combined list is the final answer.

# Solutions
### Java

```java
class Solution {
public
  int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
    int idx = m;
    List<Integer>[] groupItems = new List[n + m];
    int[] itemDegree = new int[n];
    int[] groupDegree = new int[n + m];
    List<Integer>[] itemGraph = new List[n];
    List<Integer>[] groupGraph = new List[n + m];
    Arrays.setAll(groupItems, k->new ArrayList<>());
    Arrays.setAll(itemGraph, k->new ArrayList<>());
    Arrays.setAll(groupGraph, k->new ArrayList<>());
    for (int i = 0; i < n; ++i) {
      if (group[i] == -1) {
        group[i] = idx++;
      }
      groupItems[group[i]].add(i);
    }
    for (int i = 0; i < n; ++i) {
      for (int j : beforeItems.get(i)) {
        if (group[i] == group[j]) {
          ++itemDegree[i];
          itemGraph[j].add(i);
        } else {
          ++groupDegree[group[i]];
          groupGraph[group[j]].add(group[i]);
        }
      }
    }
    List<Integer> items = new ArrayList<>();
    for (int i = 0; i < n + m; ++i) {
      items.add(i);
    }
    var groupOrder = topoSort(groupDegree, groupGraph, items);
    if (groupOrder.isEmpty()) {
      return new int[0];
    }
    List<Integer> ans = new ArrayList<>();
    for (int gi : groupOrder) {
      items = groupItems[gi];
      var itemOrder = topoSort(itemDegree, itemGraph, items);
      if (itemOrder.size() != items.size()) {
        return new int[0];
      }
      ans.addAll(itemOrder);
    }
    return ans.stream().mapToInt(Integer : : intValue).toArray();
  }
private
  List<Integer> topoSort(int[] degree, List<Integer>[] graph,
                         List<Integer> items) {
    Deque<Integer> q = new ArrayDeque<>();
    for (int i : items) {
      if (degree[i] == 0) {
        q.offer(i);
      }
    }
    List<Integer> ans = new ArrayList<>();
    while (!q.isEmpty()) {
      int i = q.poll();
      ans.add(i);
      for (int j : graph[i]) {
        if (--degree[j] == 0) {
          q.offer(j);
        }
      }
    }
    return ans.size() == items.size() ? ans : List.of();
  }
}

```

### CPP

```cpp
class Solution {
public:
  vector<int> sortItems(int n, int m, vector<int> &group,
                        vector<vector<int>> &beforeItems) {
    int idx = m;
    vector<vector<int>> groupItems(n + m);
    vector<int> itemDegree(n);
    vector<int> groupDegree(n + m);
    vector<vector<int>> itemGraph(n);
    vector<vector<int>> groupGraph(n + m);
    for (int i = 0; i < n; ++i) {
      if (group[i] == -1) {
        group[i] = idx++;
      }
      groupItems[group[i]].push_back(i);
    }
    for (int i = 0; i < n; ++i) {
      for (int j : beforeItems[i]) {
        if (group[i] == group[j]) {
          ++itemDegree[i];
          itemGraph[j].push_back(i);
        } else {
          ++groupDegree[group[i]];
          groupGraph[group[j]].push_back(group[i]);
        }
      }
    }
    vector<int> items(n + m);
    iota(items.begin(), items.end(), 0);
    auto topoSort = [](vector<vector<int>> &graph, vector<int> &degree,
                       vector<int> &items) -> vector<int> {
      queue<int> q;
      for (int &i : items) {
        if (degree[i] == 0) {
          q.push(i);
        }
      }
      vector<int> ans;
      while (!q.empty()) {
        int i = q.front();
        q.pop();
        ans.push_back(i);
        for (int &j : graph[i]) {
          if (--degree[j] == 0) {
            q.push(j);
          }
        }
      }
      return ans.size() == items.size() ? ans : vector<int>();
    };
    auto groupOrder = topoSort(groupGraph, groupDegree, items);
    if (groupOrder.empty()) {
      return vector<int>();
    }
    vector<int> ans;
    for (int &gi : groupOrder) {
      items = groupItems[gi];
      auto itemOrder = topoSort(itemGraph, itemDegree, items);
      if (items.size() != itemOrder.size()) {
        return vector<int>();
      }
      ans.insert(ans.end(), itemOrder.begin(), itemOrder.end());
    }
    return ans;
  }
};

```

### Python

```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

```