Formatted question description: https://leetcode.ca/all/1203.html

1203. Sort Items by Groups Respecting Dependencies (Hard)

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.

Related Topics:
Depth-first Search, Graph, Topological Sort

Solution 1. Topological Sort

// OJ: https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/
// Time: O(M + N + E)
// Space: O(M + N + E)
class Solution {
public:
vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
unordered_map<int, vector<int>> itemGraph; // adjacency list of items. Edges between groups are considered in groupGraph so ignored here.
unordered_map<int, vector<int>> groupGraph; // adjacency list of groups.
vector<int> itemIndegree(n); // in-degree of each item
unordered_map<int, int> groupIndegree; // in-degree of each group
unordered_map<int, vector<int>> itemInGroup; // map from group id to items in the group
for (int i = 0; i < n; ++i) {
if (group[i] == -1) group[i] = i + m; // make items without group to be in group i + m so that we can treat all the items the same
itemInGroup[group[i]].push_back(i);
}
for (int i = 0; i < beforeItems.size(); ++i) {
for (int j = 0; j < beforeItems[i].size(); ++j) {
int from = beforeItems[i][j], to = i, fromGroup = group[from], toGroup = group[to];
if (fromGroup == toGroup) { // If the edge is in the same group, update itemGraph and itemIndegree
itemGraph[from].push_back(to);
itemIndegree[to]++;
} else { // If the edge is cross groups, update groupGraph and groupIndegree
groupGraph[fromGroup].push_back(toGroup);
groupIndegree[toGroup]++;
}
}
}
queue<int> groupQueue;
for (auto &p : itemInGroup) { // Get the initial set of groups without indegree
if (groupIndegree[p.first] == 0) groupQueue.push(p.first);
}
vector<int> ans;
while (groupQueue.size()) {
int gid = groupQueue.front();
groupQueue.pop();
queue<int> itemQueue; // do topological sort within the same group
int itemCnt = 0;
for (int u : itemInGroup[gid]) {
if (itemIndegree[u] == 0) itemQueue.push(u);
}
while (itemQueue.size()) {
int itemId = itemQueue.front();
itemQueue.pop();
ans.push_back(itemId);
++itemCnt;
for (int v : itemGraph[itemId]) {
if (--itemIndegree[v] == 0) itemQueue.push(v);
}
}
if (itemCnt != itemInGroup[gid].size()) return {}; // has circle within group, return empty list
for (int v : groupGraph[gid]) {
if (--groupIndegree[v] == 0) groupQueue.push(v);
}
}
if (ans.size() != n) return {}; // has circle between group, return empty list
return ans;
}
};


Solution 2. Topological Sort

// OJ: https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/
// Time: O(M + N + E)
// Space: O(M + N + E)
class Solution {
public:
vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
unordered_map<int, vector<int>> groupGraph, groupItems;
unordered_map<int, int> groupIndegree;
vector<int> groupOrder, ans;
for (int i = 0; i < n; ++i) {
int a = group[i] == -1 ? m + i : group[i];// For those items belonging to no group, let the groupId be m + i.
if (a < m) groupItems[group[i]].push_back(i);
if (groupGraph.count(a) == 0) groupGraph[a] = {};
for (int j : beforeItems[i]) {
int b = group[j] == -1 ? m + j : group[j];
if (a == b) continue; // skip intra dependency
groupGraph[b].push_back(a);
groupIndegree[a]++;
}
}
queue<int> q;
for (auto &[g, _] : groupGraph) {
if (groupIndegree[g] == 0) q.push(g);
}
while (q.size()) {
int u = q.front();
q.pop();
groupOrder.push_back(u);
for (int v : groupGraph[u]) {
if (--groupIndegree[v] == 0) q.push(v);
}
}
if (groupOrder.size() != groupGraph.size()) return {};
for (int g : groupOrder) {
if (g >= m) {
ans.push_back(g - m);
continue;
}
unordered_map<int, vector<int>> itemGraph;
unordered_map<int, int> itemIndegree;
for (int u : groupItems[g]) {
for (int v : beforeItems[u]) {
if (group[v] != g) continue;
itemGraph[v].push_back(u);
itemIndegree[u]++;
}
}
for (int u : groupItems[g]) {
if (itemIndegree[u] == 0) q.push(u);
}
int cnt = 0;
while (q.size()) {
int u = q.front();
q.pop();
ans.push_back(u);
++cnt;
for (int v : itemGraph[u]) {
if (--itemIndegree[v] == 0) q.push(v);
}
}
if (cnt != groupItems[g].size()) return {};
}
return ans;
}
};

• class Solution {
public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
for (int i = 0; i < n; i++) {
if (group[i] == -1) {
group[i] = m;
m++;
}
}
Map<Integer, Set<Integer>> groupOrderMap = new HashMap<Integer, Set<Integer>>();
Map<Integer, Set<Integer>> itemOrderMap = new HashMap<Integer, Set<Integer>>();
for (int i = 0; i < n; i++) {
int currGroup = group[i];
List<Integer> beforeList = beforeItems.get(i);
for (int before : beforeList) {
int prevGroup = group[before];
Set<Integer> groupSet = groupOrderMap.getOrDefault(prevGroup, new HashSet<Integer>());
groupOrderMap.put(prevGroup, groupSet);
Set<Integer> itemSet = itemOrderMap.getOrDefault(before, new HashSet<Integer>());
itemOrderMap.put(before, itemSet);
}
}
int[] groupIndegrees = new int[m];
for (int i = 0; i < m; i++) {
Set<Integer> set = groupOrderMap.getOrDefault(i, new HashSet<Integer>());
for (int nextGroup : set) {
if (nextGroup != i)
groupIndegrees[nextGroup]++;
}
}
for (int i = 0; i < m; i++) {
if (groupIndegrees[i] == 0)
groupQueue.offer(i);
}
int[] groupsOrder = new int[m];
int groupIndex = 0;
while (!groupQueue.isEmpty()) {
int currGroup = groupQueue.poll();
groupsOrder[groupIndex] = currGroup;
groupIndex++;
Set<Integer> set = groupOrderMap.getOrDefault(currGroup, new HashSet<Integer>());
for (int nextGroup : set) {
groupIndegrees[nextGroup]--;
if (groupIndegrees[nextGroup] == 0)
groupQueue.offer(nextGroup);
}
}
if (groupIndex < m)
return new int[0];
Map<Integer, Set<Integer>> groupItemsMap = new HashMap<Integer, Set<Integer>>();
for (int i = 0; i < n; i++) {
int currGroup = group[i];
Set<Integer> set = groupItemsMap.getOrDefault(currGroup, new HashSet<Integer>());
groupItemsMap.put(currGroup, set);
}
int[] itemIndegrees = new int[n];
for (int i = 0; i < n; i++) {
Set<Integer> set = itemOrderMap.getOrDefault(i, new HashSet<Integer>());
for (int nextItem : set)
itemIndegrees[nextItem]++;
}
int[] itemsOrder = new int[n];
int itemIndex = 0;
for (int i = 0; i < m; i++) {
int currGroup = groupsOrder[i];
Set<Integer> itemSet = groupItemsMap.getOrDefault(currGroup, new HashSet<Integer>());
for (int item : itemSet) {
if (itemIndegrees[item] == 0)
itemQueue.offer(item);
}
while (!itemQueue.isEmpty()) {
int item = itemQueue.poll();
itemsOrder[itemIndex] = item;
itemIndex++;
Set<Integer> set = itemOrderMap.getOrDefault(item, new HashSet<Integer>());
for (int nextItem : set) {
itemIndegrees[nextItem]--;
if (itemIndegrees[nextItem] == 0 && group[nextItem] == currGroup)
itemQueue.offer(nextItem);
}
}
}
if (itemIndex < n)
return new int[0];
else
return itemsOrder;
}
}

• 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


• func sortItems(n int, m int, group []int, beforeItems [][]int) []int {
idx := m
groupItems := make([][]int, n+m)
itemDegree := make([]int, n)
groupDegree := make([]int, n+m)
itemGraph := make([][]int, n)
groupGraph := make([][]int, n+m)
for i, g := range group {
if g == -1 {
group[i] = idx
idx++
}
groupItems[group[i]] = append(groupItems[group[i]], i)
}
for i, gi := range group {
for _, j := range beforeItems[i] {
gj := group[j]
if gi == gj {
itemDegree[i]++
itemGraph[j] = append(itemGraph[j], i)
} else {
groupDegree[gi]++
groupGraph[gj] = append(groupGraph[gj], gi)
}
}
}
items := make([]int, n+m)
for i := range items {
items[i] = i
}
topoSort := func(degree []int, graph [][]int, items []int) []int {
q := []int{}
for _, i := range items {
if degree[i] == 0 {
q = append(q, i)
}
}
ans := []int{}
for len(q) > 0 {
i := q[0]
q = q[1:]
ans = append(ans, i)
for _, j := range graph[i] {
degree[j]--
if degree[j] == 0 {
q = append(q, j)
}
}
}
return ans
}
groupOrder := topoSort(groupDegree, groupGraph, items)
if len(groupOrder) != len(items) {
return nil
}
ans := []int{}
for _, gi := range groupOrder {
items = groupItems[gi]
itemOrder := topoSort(itemDegree, itemGraph, items)
if len(items) != len(itemOrder) {
return nil
}
ans = append(ans, itemOrder...)
}
return ans
}

• function sortItems(
n: number,
m: number,
group: number[],
beforeItems: number[][],
): number[] {
let idx = m;
const groupItems: number[][] = new Array(n + m).fill(0).map(() => []);
const itemDegree: number[] = new Array(n).fill(0);
const gorupDegree: number[] = new Array(n + m).fill(0);
const itemGraph: number[][] = new Array(n).fill(0).map(() => []);
const groupGraph: number[][] = new Array(n + m).fill(0).map(() => []);
for (let i = 0; i < n; ++i) {
if (group[i] === -1) {
group[i] = idx++;
}
groupItems[group[i]].push(i);
}
for (let i = 0; i < n; ++i) {
for (const j of beforeItems[i]) {
if (group[i] === group[j]) {
++itemDegree[i];
itemGraph[j].push(i);
} else {
++gorupDegree[group[i]];
groupGraph[group[j]].push(group[i]);
}
}
}
let items = new Array(n + m).fill(0).map((_, i) => i);
const topoSort = (
graph: number[][],
degree: number[],
items: number[],
): number[] => {
const q: number[] = [];
for (const i of items) {
if (degree[i] === 0) {
q.push(i);
}
}
const ans: number[] = [];
while (q.length) {
const i = q.pop()!;
ans.push(i);
for (const j of graph[i]) {
if (--degree[j] === 0) {
q.push(j);
}
}
}
return ans.length === items.length ? ans : [];
};
const groupOrder = topoSort(groupGraph, gorupDegree, items);
if (groupOrder.length === 0) {
return [];
}
const ans: number[] = [];
for (const gi of groupOrder) {
items = groupItems[gi];
const itemOrder = topoSort(itemGraph, itemDegree, items);
if (itemOrder.length !== items.length) {
return [];
}
ans.push(...itemOrder);
}
return ans;
}