class Solution { public int[] sortItems(int n, int m, int[] group, List> beforeItems) { // Initialize the group ids for standalone items. for (int i = 0; i < n; i++) { if (group[i] == -1) { group[i] = m++; } } // Create adjacency lists for items and groups. List[] itemGraph = new List[n]; List[] groupGraph = new List[m]; for (int i = 0; i < n; i++) { itemGraph[i] = new ArrayList<>(); } for (int i = 0; i < m; i++) { groupGraph[i] = new ArrayList<>(); } // Indegree arrays for topological sorting. int[] itemIndegree = new int[n]; int[] groupIndegree = new int[m]; // Populate the graphs. for (int i = 0; i < n; i++) { int currGroup = group[i]; for (int beforeItem : beforeItems.get(i)) { // Add edge in the item graph. itemGraph[beforeItem].add(i); itemIndegree[i]++; int beforeGroup = group[beforeItem]; if (beforeGroup != currGroup) { // Add edge in the group graph if in different groups. groupGraph[beforeGroup].add(currGroup); groupIndegree[currGroup]++; } } } // Topological sort for the groups. List sortedGroups = topologicalSort(groupGraph, groupIndegree, m); if (sortedGroups == null) return new int[0]; // Topological sort for individuals in each group. List result = new ArrayList<>(); for (int grp : sortedGroups) { List itemsInGroup = new ArrayList<>(); for (int i = 0; i < n; i++) { if (group[i] == grp) { itemsInGroup.add(i); } } List sortedItems = topologicalSort(itemGraph, itemIndegree, itemsInGroup.size(), itemsInGroup); if (sortedItems == null) return new int[0]; result.addAll(sortedItems); } return result.stream().mapToInt(i -> i).toArray(); } private List topologicalSort(List[] graph, int[] indegree, int total, List nodes) { Queue queue = new LinkedList<>(); for (int node : nodes) { if (indegree[node] == 0) { queue.add(node); } } List sorted = new ArrayList<>(); while (!queue.isEmpty()) { int node = queue.poll(); sorted.add(node); for (int neighbor : graph[node]) { indegree[neighbor]--; if (indegree[neighbor] == 0) { queue.add(neighbor); } } } return sorted.size() == total ? sorted : null; } private List topologicalSort(List[] graph, int[] indegree, int size) { return topologicalSort(graph, indegree, size, generateRange(size)); } private List generateRange(int n) { List range = new ArrayList<>(n); for (int i = 0; i < n; i++) { range.add(i); } return range; } }

Sort Items by Groups Respecting Dependencies

Written by Rahul Aher