Sort Items by Groups Respecting Dependencies solution and explanation

from collections import defaultdict, deque

def topologicalSort(n, adjList, indegree):
    order = []
    zeroIndegree = deque([i for i in range(n) if indegree[i] == 0])
    while zeroIndegree:
        node = zeroIndegree.popleft()
        order.append(node)
        for neighbor in adjList[node]:
            indegree[neighbor] -= 1
            if indegree[neighbor] == 0:
                zeroIndegree.append(neighbor)
    return order if len(order) == n else []


def sortItems(n, m, group, beforeItems):
    # Step 1: Assign temporary groups to items with a group of -1.
    new_group = m  # Start numbering new groups from m
    for i in range(n):
        if group[i] == -1:
            group[i] = new_group
            new_group += 1

    # Step 2: Item graph and indegree
    item_graph = defaultdict(list)
    item_indegree = [0] * n

    # Step 3: Group graph and indegree
    group_graph = defaultdict(list)
    group_indegree = [0] * new_group

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

    # Step 4: Topological sort groups and items
    group_order = topologicalSort(new_group, group_graph, group_indegree)
    if not group_order:
        return []

    item_order = topologicalSort(n, item_graph, item_indegree)
    if not item_order:
        return []

    # Step 5: Map order back to the result by groups
    items_by_group = defaultdict(list)
    for item in item_order:
        items_by_group[group[item]].append(item)

    result = []
    for grp in group_order:
        result.extend(items_by_group[grp])

    return result

import java.util.*;

public class Solution {
    public List<Integer> sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        // Assign unique groups to those without any starting group
        int newGroupId = m;
        for (int i = 0; i < n; i++) {
            if (group[i] == -1) {
                group[i] = newGroupId++;
            }
        }

        // Initialize group and item graphs
        List<Integer>[] itemGraph = new ArrayList[n];
        List<Integer>[] groupGraph = new ArrayList[newGroupId];
        int[] itemIndegree = new int[n];
        int[] groupIndegree = new int[newGroupId];

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

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

        // Build the graphs for items and groups
        for (int i = 0; i < n; i++) {
            for (int before : beforeItems.get(i)) {
                itemGraph[before].add(i);
                itemIndegree[i]++;
                if (group[i] != group[before]) {
                    groupGraph[group[before]].add(group[i]);
                    groupIndegree[group[i]]++;
                }
            }
        }

        // Get sorted orders
        List<Integer> groupOrder = topologicalSort(newGroupId, groupGraph, groupIndegree);
        if (groupOrder.isEmpty()) return new ArrayList<>();

        List<Integer> itemOrder = topologicalSort(n, itemGraph, itemIndegree);
        if (itemOrder.isEmpty()) return new ArrayList<>();

        // Sort items by group order
        List<Integer>[] itemsWithGroupOrder = new ArrayList[newGroupId];
        for (int i = 0; i < newGroupId; i++) {
            itemsWithGroupOrder[i] = new ArrayList<>();
        }

        for (int item : itemOrder) {
            itemsWithGroupOrder[group[item]].add(item);
        }

        List<Integer> result = new ArrayList<>();
        for (int grp : groupOrder) {
            result.addAll(itemsWithGroupOrder[grp]);
        }

        return result;
    }

    private List<Integer> topologicalSort(int n, List<Integer>[] graph, int[] indegree) {
        Queue<Integer> zeroIndegree = new LinkedList<>();
        List<Integer> order = new ArrayList<>();

        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                zeroIndegree.offer(i);
            }
        }

        while (!zeroIndegree.isEmpty()) {
            int node = zeroIndegree.poll();
            order.add(node);
            for (int neighbor : graph[node]) {
                indegree[neighbor]--;
                if (indegree[neighbor] == 0) {
                    zeroIndegree.offer(neighbor);
                }
            }
        }

        return order.size() == n ? order : new ArrayList<>();
    }
}

#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>

using namespace std;

vector<int> topologicalSortUsingPQ(int n, vector<vector<int>>& graph, vector<int>& indegree) {
    priority_queue<int, vector<int>, greater<int>> zeroIndegree;
    vector<int> order;
    for (int i = 0; i < n; ++i) {
        if (indegree[i] == 0) {
            zeroIndegree.push(i);
        }
    }
    
    while (!zeroIndegree.empty()) {
        int node = zeroIndegree.top();
        zeroIndegree.pop();
        order.push_back(node);
        for (int neighbor : graph[node]) {
            if (--indegree[neighbor] == 0) {
                zeroIndegree.push(neighbor);
            }
        }
    }
    return order.size() == n ? order : vector<int>();
}

vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
    int newGroupId = m;
    for (int i = 0; i < n; ++i) {
        if (group[i] == -1) {
            group[i] = newGroupId++;
        }
    }

    vector<vector<int>> itemGraph(n), groupGraph(newGroupId);
    vector<int> itemIndegree(n, 0), groupIndegree(newGroupId, 0);

    for (int i = 0; i < n; ++i) {
        for (int before : beforeItems[i]) {
            itemGraph[before].push_back(i);
            ++itemIndegree[i];
            if (group[i] != group[before]) {
                groupGraph[group[before]].push_back(group[i]);
                ++groupIndegree[group[i]];
            }
        }
    }

    vector<int> groupOrder = topologicalSortUsingPQ(newGroupId, groupGraph, groupIndegree);
    if (groupOrder.empty()) return {};

    vector<int> itemOrder = topologicalSortUsingPQ(n, itemGraph, itemIndegree);
    if (itemOrder.empty()) return {};

    unordered_map<int, vector<int>> itemsGrouped;
    for (int item : itemOrder) {
        itemsGrouped[group[item]].push_back(item);
    }

    vector<int> result;
    for (int grp : groupOrder) {
        result.insert(result.end(), itemsGrouped[grp].begin(), itemsGrouped[grp].end());
    }

    return result;
}

using System;
using System.Collections.Generic;

public class Solution {
    public IList<int> SortItems(int n, int m, int[] group, IList<IList<int>> beforeItems) {
        int newGroupId = m;
        for (int i = 0; i < n; ++i) {
            if (group[i] == -1) {
                group[i] = newGroupId++;
            }
        }

        List<int>[] itemGraph = new List<int>[n], groupGraph = new List<int>[newGroupId];
        int[] itemIndegree = new int[n], groupIndegree = new int[newGroupId];

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

        for (int i = 0; i < newGroupId; i++) {
            groupGraph[i] = new List<int>();
        }

        for (int i = 0; i < n; i++) {
            foreach (var before in beforeItems[i]) {
                itemGraph[before].Add(i);
                itemIndegree[i]++;
                if (group[i] != group[before]) {
                    groupGraph[group[before]].Add(group[i]);
                    groupIndegree[group[i]]++;
                }
            }
        }

        var groupOrder = pqTopologicalSort(newGroupId, groupGraph, groupIndegree);
        if (groupOrder.Count == 0) return new List<int>();

        var itemOrder = pqTopologicalSort(n, itemGraph, itemIndegree);
        if (itemOrder.Count == 0) return new List<int>();

        var itemsGrouped = new Dictionary<int, List<int>>();
        foreach (var item in itemOrder) {
            if (!itemsGrouped.ContainsKey(group[item])) {
                itemsGrouped[group[item]] = new List<int>();
            }
            itemsGrouped[group[item]].Add(item);
        }

        var result = new List<int>();
        foreach (var grp in groupOrder) {
            if (itemsGrouped.ContainsKey(grp)) {
                result.AddRange(itemsGrouped[grp]);
            }
        }

        return result;
    }

    private List<int> pqTopologicalSort(int n, List<int>[] graph, int[] indegree) {
        var zeroIndegree = new SortedSet<int>();
        var order = new List<int>();

        for (int i = 0; i < n; i++) {
            if (indegree[i] == 0) {
                zeroIndegree.Add(i);
            }
        }

        while (zeroIndegree.Count > 0) {
            int node = zeroIndegree.Min;
            zeroIndegree.Remove(node);
            order.Add(node);
            foreach (var neighbor in graph[node]) {
                if (--indegree[neighbor] == 0) {
                    zeroIndegree.Add(neighbor);
                }
            }
        }

        return order.Count == n ? order : new List<int>();
    }
}

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;
}

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
}