1203. Sort Items by Groups Respecting Dependencies

public class Solution {
    public int[] SortItems(int n, int m, int[] group, IList<IList<int>> beforeItems) {
        int groupId = m;
        for (int i = 0; i < n; i++) if (group[i] == -1) group[i] = groupId++;
        var itemGraph = new Dictionary<int, List<int>>();
        var groupGraph = new Dictionary<int, List<int>>();
        int[] itemIndegree = new int[n], groupIndegree = new int[groupId];
        for (int i = 0; i < n; i++) itemGraph[i] = new List<int>();
        for (int i = 0; i < groupId; i++) groupGraph[i] = new List<int>();
        for (int curr = 0; curr < n; curr++) {
            foreach (var prev in beforeItems[curr]) {
                itemGraph[prev].Add(curr);
                itemIndegree[curr]++;
                if (group[curr] != group[prev]) {
                    groupGraph[group[prev]].Add(group[curr]);
                    groupIndegree[group[curr]]++;
                }
            }
        }
        var itemOrder = TopologicalSort(itemGraph, itemIndegree);
        var groupOrder = TopologicalSort(groupGraph, groupIndegree);
        if (itemOrder.Count == 0 || groupOrder.Count == 0) return new int[0];
        var orderedGroups = new Dictionary<int, List<int>>();
        foreach (var item in itemOrder) {
            if (!orderedGroups.ContainsKey(group[item])) orderedGroups[group[item]] = new List<int>();
            orderedGroups[group[item]].Add(item);
        }
        var answerList = new List<int>();
        foreach (var groupIndex in groupOrder) {
            if (orderedGroups.ContainsKey(groupIndex)) answerList.AddRange(orderedGroups[groupIndex]);
        }
        return answerList.ToArray();
    }
    private List<int> TopologicalSort(Dictionary<int, List<int>> graph, int[] indegree) {
        var visited = new List<int>();
        var stack = new Stack<int>();
        foreach (var key in graph.Keys) if (indegree[key] == 0) stack.Push(key);
        while (stack.Count > 0) {
            var curr = stack.Pop();
            visited.Add(curr);
            foreach (var next in graph[curr]) if (--indegree[next] == 0) stack.Push(next);
        }
        return visited.Count == graph.Keys.Count ? visited : new List<int>();
    }
}

#include <bits/stdc++.h>
using namespace std;

// Auto-generated C++ draft from the C# solution. Review containers, LINQ and helper types before submit.
class Solution {
public:
    public vector<int>& SortItems(int n, int m, vector<int>& group, IList<vector<int>> beforeItems) {
        int groupId = m;
        for (int i = 0; i < n; i++) if (group[i] == -1) group[i] = groupId++;
        var itemGraph = new unordered_map<int, List<int>>();
        var groupGraph = new unordered_map<int, List<int>>();
        vector<int>& itemIndegree = new int[n], groupIndegree = new int[groupId];
        for (int i = 0; i < n; i++) itemGraph[i] = new List<int>();
        for (int i = 0; i < groupId; i++) groupGraph[i] = new List<int>();
        for (int curr = 0; curr < n; curr++) {
            foreach (var prev in beforeItems[curr]) {
                itemGraph[prev].push_back(curr);
                itemIndegree[curr]++;
                if (group[curr] != group[prev]) {
                    groupGraph[group[prev]].push_back(group[curr]);
                    groupIndegree[group[curr]]++;
                }
            }
        }
        var itemOrder = TopologicalSort(itemGraph, itemIndegree);
        var groupOrder = TopologicalSort(groupGraph, groupIndegree);
        if (itemOrder.size() == 0 || groupOrder.size() == 0) return new int[0];
        var orderedGroups = new unordered_map<int, List<int>>();
        foreach (var item in itemOrder) {
            if (!orderedGroups.count(group[item])) orderedGroups[group[item]] = new List<int>();
            orderedGroups[group[item]].push_back(item);
        }
        var answerList = new List<int>();
        foreach (var groupIndex in groupOrder) {
            if (orderedGroups.count(groupIndex)) answerList.AddRange(orderedGroups[groupIndex]);
        }
        return answerList.ToArray();
    }
    private List<int> TopologicalSort(unordered_map<int, List<int>> graph, vector<int>& indegree) {
        var visited = new List<int>();
        var stack = new stack<int>();
        foreach (var key in graph.Keys) if (indegree[key] == 0) stack.push(key);
        while (stack.size() > 0) {
            var curr = stack.pop();
            visited.push_back(curr);
            foreach (var next in graph[curr]) if (--indegree[next] == 0) stack.push(next);
        }
        return visited.size() == graph.Keys.size() ? visited : new List<int>();
    }
}

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        int groupId = m;
        for (int i = 0; i < n; i++) if (group[i] == -1) group[i] = groupId++;

        Map<Integer, List<Integer>> itemGraph = new HashMap<>();
        Map<Integer, List<Integer>> groupGraph = new HashMap<>();
        int[] itemIndegree = new int[n], groupIndegree = new int[groupId];
        for (int i = 0; i < n; i++) itemGraph.put(i, new ArrayList<>());
        for (int i = 0; i < groupId; i++) groupGraph.put(i, new ArrayList<>());

        for (int curr = 0; curr < n; curr++) {
            for (int prev : beforeItems.get(curr)) {
                itemGraph.get(prev).add(curr);
                itemIndegree[curr]++;
                if (group[curr] != group[prev]) {
                    groupGraph.get(group[prev]).add(group[curr]);
                    groupIndegree[group[curr]]++;
                }
            }
        }

        List<Integer> itemOrder = topologicalSort(itemGraph, itemIndegree);
        List<Integer> groupOrder = topologicalSort(groupGraph, groupIndegree);
        if (itemOrder.isEmpty() || groupOrder.isEmpty()) return new int[0];

        Map<Integer, List<Integer>> orderedGroups = new HashMap<>();
        for (int item : itemOrder) orderedGroups.computeIfAbsent(group[item], k -> new ArrayList<>()).add(item);

        List<Integer> answerList = new ArrayList<>();
        for (int groupIndex : groupOrder) answerList.addAll(orderedGroups.getOrDefault(groupIndex, new ArrayList<>()));

        return answerList.stream().mapToInt(Integer::intValue).toArray();
    }

    private List<Integer> topologicalSort(Map<Integer, List<Integer>> graph, int[] indegree) {
        List<Integer> visited = new ArrayList<>();
        Stack<Integer> stack = new Stack<>();
        for (int key : graph.keySet()) if (indegree[key] == 0) stack.add(key);

        while (!stack.isEmpty()) {
            int curr = stack.pop();
            visited.add(curr);
            for (int next : graph.get(curr)) if (--indegree[next] == 0) stack.add(next);
        }

        return visited.size() == graph.size() ? visited : new ArrayList<>();
    }
}

var sortItems = function(n, m, group, beforeItems) {
    let groupId = m;
    for (let i = 0; i < n; i++) if (group[i] === -1) group[i] = groupId++;

    const itemGraph = new Map();
    const groupGraph = new Map();
    const itemIndegree = Array(n).fill(0);
    const groupIndegree = Array(groupId).fill(0);
    for (let i = 0; i < n; i++) itemGraph.set(i, []);
    for (let i = 0; i < groupId; i++) groupGraph.set(i, []);

    for (let curr = 0; curr < n; curr++) {
        for (const prev of beforeItems[curr]) {
            itemGraph.get(prev).push(curr);
            itemIndegree[curr]++;
            if (group[curr] !== group[prev]) {
                groupGraph.get(group[prev]).push(group[curr]);
                groupIndegree[group[curr]]++;
            }
        }
    }

    const itemOrder = topologicalSort(itemGraph, itemIndegree);
    const groupOrder = topologicalSort(groupGraph, groupIndegree);
    if (itemOrder.length === 0 || groupOrder.length === 0) return [];

    const orderedGroups = new Map();
    for (const item of itemOrder) {
        if (!orderedGroups.has(group[item])) orderedGroups.set(group[item], []);
        orderedGroups.get(group[item]).push(item);
    }

    const answerList = [];
    for (const groupIndex of groupOrder) {
        if (orderedGroups.has(groupIndex)) answerList.push(...orderedGroups.get(groupIndex));
    }

    return answerList;
};

function topologicalSort(graph, indegree) {
    const visited = [];
    const stack = [];
    for (const [key] of graph.entries()) if (indegree[key] === 0) stack.push(key);

    while (stack.length > 0) {
        const curr = stack.pop();
        visited.push(curr);
        for (const next of graph.get(curr)) {
            indegree[next]--;
            if (indegree[next] === 0) stack.push(next);
        }
    }

    return visited.length === graph.size ? visited : [];
}

func sortItems(n int, m int, group []int, beforeItems [][]int) []int {
    groupId := m
    for i := 0; i < n; i++ {
        if group[i] == -1 {
            group[i] = groupId
            groupId++
        }
    }

    itemGraph := make(map[int][]int)
    groupGraph := make(map[int][]int)
    itemIndegree := make([]int, n)
    groupIndegree := make([]int, groupId)

    for i := 0; i < n; i++ {
        itemGraph[i] = []int{}
    }
    for i := 0; i < groupId; i++ {
        groupGraph[i] = []int{}
    }

    for curr := 0; curr < n; curr++ {
        for _, prev := range beforeItems[curr] {
            itemGraph[prev] = append(itemGraph[prev], curr)
            itemIndegree[curr]++
            if group[curr] != group[prev] {
                groupGraph[group[prev]] = append(groupGraph[group[prev]], group[curr])
                groupIndegree[group[curr]]++
            }
        }
    }

    itemOrder := topologicalSort(itemGraph, itemIndegree)
    groupOrder := topologicalSort(groupGraph, groupIndegree)
    if len(itemOrder) == 0 || len(groupOrder) == 0 {
        return []int{}
    }

    orderedGroups := make(map[int][]int)
    for _, item := range itemOrder {
        orderedGroups[group[item]] = append(orderedGroups[group[item]], item)
    }

    answerList := []int{}
    for _, groupIndex := range groupOrder {
        answerList = append(answerList, orderedGroups[groupIndex]...)
    }

    return answerList
}

func topologicalSort(graph map[int][]int, indegree []int) []int {
    visited := []int{}
    stack := []int{}
    for key := range graph {
        if indegree[key] == 0 {
            stack = append(stack, key)
        }
    }

    for len(stack) > 0 {
        curr := stack[len(stack)-1]
        stack = stack[:len(stack)-1]
        visited = append(visited, curr)
        for _, next := range graph[curr] {
            indegree[next]--
            if indegree[next] == 0 {
                stack = append(stack, next)
            }
        }
    }

    if len(visited) != len(graph) {
        return []int{}
    }
    return visited
}