Sort Items by Groups Respecting Dependencies
HardUpdated: Sep 1, 2025
Practice on:
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 thei-th item in the sorted array (to the left of thei-th item).
Return any solution if there is more than one solution and return an empty list if there is no solution.
Examples
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^4group.length == beforeItems.length == n-1 <= group[i] <= m - 10 <= beforeItems[i].length <= n - 10 <= beforeItems[i][j] <= n - 1i != beforeItems[i][j]beforeItems[i]does not contain duplicates elements.
Solution
Method 1 - Dual Topological Sort
Intuition
This problem requires two levels of topological sorting: first sort the groups, then sort items within each group. We need to handle dependencies both between groups and within groups.
Approach
- Assign unique group IDs to items with group -1 (no group)
- Build two dependency graphs: one for groups and one for items
- Perform topological sort on groups to get group order
- For each group, perform topological sort on its items
- Combine results respecting group order and item dependencies
Code
C++
#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;
vector<int> topSort(vector<vector<int>>& graph, vector<int>& indegree) {
queue<int> q;
vector<int> result;
for (int i = 0; i < indegree.size(); i++) {
if (indegree[i] == 0) {
q.push(i);
}
}
while (!q.empty()) {
int node = q.front();
q.pop();
result.push_back(node);
for (int neighbor : graph[node]) {
indegree[neighbor]--;
if (indegree[neighbor] == 0) {
q.push(neighbor);
}
}
}
return result;
}
vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
// Assign unique group IDs to items without groups
int groupId = m;
for (int i = 0; i < n; i++) {
if (group[i] == -1) {
group[i] = groupId++;
}
}
// Build group graph and item graph
vector<vector<int>> groupGraph(groupId);
vector<int> groupIndegree(groupId, 0);
vector<vector<int>> itemGraph(n);
vector<int> itemIndegree(n, 0);
for (int i = 0; i < n; i++) {
for (int prev : beforeItems[i]) {
// Item dependency
itemGraph[prev].push_back(i);
itemIndegree[i]++;
// Group dependency (if different groups)
if (group[prev] != group[i]) {
groupGraph[group[prev]].push_back(group[i]);
groupIndegree[group[i]]++;
}
}
}
// Topological sort for groups
vector<int> groupOrder = topSort(groupGraph, groupIndegree);
if (groupOrder.size() != groupId) {
return {}; // Cycle detected
}
// Topological sort for items
vector<int> itemOrder = topSort(itemGraph, itemIndegree);
if (itemOrder.size() != n) {
return {}; // Cycle detected
}
// Group items by their groups
unordered_map<int, vector<int>> groupToItems;
for (int item : itemOrder) {
groupToItems[group[item]].push_back(item);
}
// Build final result respecting group order
vector<int> result;
for (int g : groupOrder) {
for (int item : groupToItems[g]) {
result.push_back(item);
}
}
return result;
}
Go
func topSort(graph [][]int, indegree []int) []int {
var queue []int
var result []int
for i, deg := range indegree {
if deg == 0 {
queue = append(queue, i)
}
}
for len(queue) > 0 {
node := queue[0]
queue = queue[1:]
result = append(result, node)
for _, neighbor := range graph[node] {
indegree[neighbor]--
if indegree[neighbor] == 0 {
queue = append(queue, neighbor)
}
}
}
return result
}
func sortItems(n int, m int, group []int, beforeItems [][]int) []int {
// Assign unique group IDs
groupId := m
for i := 0; i < n; i++ {
if group[i] == -1 {
group[i] = groupId
groupId++
}
}
// Build graphs
groupGraph := make([][]int, groupId)
groupIndegree := make([]int, groupId)
itemGraph := make([][]int, n)
itemIndegree := make([]int, n)
for i := 0; i < n; i++ {
for _, prev := range beforeItems[i] {
itemGraph[prev] = append(itemGraph[prev], i)
itemIndegree[i]++
if group[prev] != group[i] {
groupGraph[group[prev]] = append(groupGraph[group[prev]], group[i])
groupIndegree[group[i]]++
}
}
}
// Topological sorts
groupOrder := topSort(groupGraph, groupIndegree)
if len(groupOrder) != groupId {
return []int{}
}
itemOrder := topSort(itemGraph, itemIndegree)
if len(itemOrder) != n {
return []int{}
}
// Group items
groupToItems := make(map[int][]int)
for _, item := range itemOrder {
g := group[item]
groupToItems[g] = append(groupToItems[g], item)
}
// Build result
var result []int
for _, g := range groupOrder {
result = append(result, groupToItems[g]...)
}
return result
}
Java
import java.util.*;
class Solution {
public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
// Assign unique group IDs to items without groups
int groupId = m;
for (int i = 0; i < n; i++) {
if (group[i] == -1) {
group[i] = groupId++;
}
}
// Build group graph and item graph
List<List<Integer>> groupGraph = new ArrayList<>();
int[] groupIndegree = new int[groupId];
List<List<Integer>> itemGraph = new ArrayList<>();
int[] itemIndegree = new int[n];
for (int i = 0; i < groupId; i++) {
groupGraph.add(new ArrayList<>());
}
for (int i = 0; i < n; i++) {
itemGraph.add(new ArrayList<>());
}
for (int i = 0; i < n; i++) {
for (int prev : beforeItems.get(i)) {
// Item dependency
itemGraph.get(prev).add(i);
itemIndegree[i]++;
// Group dependency
if (group[prev] != group[i]) {
groupGraph.get(group[prev]).add(group[i]);
groupIndegree[group[i]]++;
}
}
}
// Topological sort for groups
List<Integer> groupOrder = topSort(groupGraph, groupIndegree);
if (groupOrder.size() != groupId) return new int[0];
// Topological sort for items
List<Integer> itemOrder = topSort(itemGraph, itemIndegree);
if (itemOrder.size() != n) return new int[0];
// Group items by their groups
Map<Integer, List<Integer>> groupToItems = new HashMap<>();
for (int item : itemOrder) {
groupToItems.computeIfAbsent(group[item], k -> new ArrayList<>()).add(item);
}
// Build final result
List<Integer> result = new ArrayList<>();
for (int g : groupOrder) {
if (groupToItems.containsKey(g)) {
result.addAll(groupToItems.get(g));
}
}
return result.stream().mapToInt(i -> i).toArray();
}
private List<Integer> topSort(List<List<Integer>> graph, int[] indegree) {
Queue<Integer> queue = new LinkedList<>();
List<Integer> result = new ArrayList<>();
for (int i = 0; i < indegree.length; i++) {
if (indegree[i] == 0) {
queue.offer(i);
}
}
while (!queue.isEmpty()) {
int node = queue.poll();
result.add(node);
for (int neighbor : graph.get(node)) {
indegree[neighbor]--;
if (indegree[neighbor] == 0) {
queue.offer(neighbor);
}
}
}
return result;
}
}
Kotlin
import java.util.*
class Solution {
fun sortItems(n: Int, m: Int, group: IntArray, beforeItems: List<List<Int>>): IntArray {
// Assign unique group IDs
var groupId = m
for (i in 0 until n) {
if (group[i] == -1) {
group[i] = groupId++
}
}
// Build graphs
val groupGraph = Array(groupId) { mutableListOf<Int>() }
val groupIndegree = IntArray(groupId)
val itemGraph = Array(n) { mutableListOf<Int>() }
val itemIndegree = IntArray(n)
for (i in 0 until n) {
for (prev in beforeItems[i]) {
itemGraph[prev].add(i)
itemIndegree[i]++
if (group[prev] != group[i]) {
groupGraph[group[prev]].add(group[i])
groupIndegree[group[i]]++
}
}
}
// Topological sorts
val groupOrder = topSort(groupGraph.map { it.toList() }, groupIndegree)
if (groupOrder.size != groupId) return intArrayOf()
val itemOrder = topSort(itemGraph.map { it.toList() }, itemIndegree)
if (itemOrder.size != n) return intArrayOf()
// Group items
val groupToItems = mutableMapOf<Int, MutableList<Int>>()
for (item in itemOrder) {
groupToItems.computeIfAbsent(group[item]) { mutableListOf() }.add(item)
}
// Build result
val result = mutableListOf<Int>()
for (g in groupOrder) {
groupToItems[g]?.let { result.addAll(it) }
}
return result.toIntArray()
}
private fun topSort(graph: List<List<Int>>, indegree: IntArray): List<Int> {
val queue: Queue<Int> = LinkedList()
val result = mutableListOf<Int>()
val indegreeCopy = indegree.clone()
for (i in indegreeCopy.indices) {
if (indegreeCopy[i] == 0) {
queue.offer(i)
}
}
while (queue.isNotEmpty()) {
val node = queue.poll()
result.add(node)
for (neighbor in graph[node]) {
indegreeCopy[neighbor]--
if (indegreeCopy[neighbor] == 0) {
queue.offer(neighbor)
}
}
}
return result
}
}
Python
from collections import defaultdict, deque
def sortItems(n: int, m: int, group: list[int], beforeItems: list[list[int]]) -> list[int]:
def topological_sort(graph, indegree):
queue = deque([i for i in range(len(indegree)) if indegree[i] == 0])
result = []
while queue:
node = queue.popleft()
result.append(node)
for neighbor in graph[node]:
indegree[neighbor] -= 1
if indegree[neighbor] == 0:
queue.append(neighbor)
return result
# Assign unique group IDs to items without groups
group_id = m
for i in range(n):
if group[i] == -1:
group[i] = group_id
group_id += 1
# Build group graph and item graph
group_graph = defaultdict(list)
group_indegree = [0] * group_id
item_graph = defaultdict(list)
item_indegree = [0] * n
for i in range(n):
for prev in beforeItems[i]:
# Item dependency
item_graph[prev].append(i)
item_indegree[i] += 1
# Group dependency (if different groups)
if group[prev] != group[i]:
group_graph[group[prev]].append(group[i])
group_indegree[group[i]] += 1
# Topological sort for groups
group_order = topological_sort(group_graph, group_indegree)
if len(group_order) != group_id:
return [] # Cycle detected
# Topological sort for items
item_order = topological_sort(item_graph, item_indegree)
if len(item_order) != n:
return [] # Cycle detected
# Group items by their groups
group_to_items = defaultdict(list)
for item in item_order:
group_to_items[group[item]].append(item)
# Build final result respecting group order
result = []
for g in group_order:
result.extend(group_to_items[g])
return result
Rust
use std::collections::{HashMap, VecDeque};
pub fn sort_items(n: i32, m: i32, mut group: Vec<i32>, before_items: Vec<Vec<i32>>) -> Vec<i32> {
let n = n as usize;
let mut group_id = m;
// Assign unique group IDs
for i in 0..n {
if group[i] == -1 {
group[i] = group_id;
group_id += 1;
}
}
let group_id = group_id as usize;
// Build graphs
let mut group_graph = vec![Vec::new(); group_id];
let mut group_indegree = vec![0; group_id];
let mut item_graph = vec![Vec::new(); n];
let mut item_indegree = vec![0; n];
for i in 0..n {
for &prev in &before_items[i] {
let prev = prev as usize;
item_graph[prev].push(i);
item_indegree[i] += 1;
if group[prev] != group[i] {
let prev_group = group[prev] as usize;
let curr_group = group[i] as usize;
group_graph[prev_group].push(curr_group);
group_indegree[curr_group] += 1;
}
}
}
// Topological sorts
let group_order = topological_sort(&group_graph, &mut group_indegree.clone());
if group_order.len() != group_id {
return vec![];
}
let item_order = topological_sort(&item_graph, &mut item_indegree.clone());
if item_order.len() != n {
return vec![];
}
// Group items
let mut group_to_items: HashMap<usize, Vec<usize>> = HashMap::new();
for item in item_order {
let g = group[item] as usize;
group_to_items.entry(g).or_insert_with(Vec::new).push(item);
}
// Build result
let mut result = Vec::new();
for g in group_order {
if let Some(items) = group_to_items.get(&g) {
result.extend(items.iter().map(|&x| x as i32));
}
}
result
}
fn topological_sort(graph: &[Vec<usize>], indegree: &mut [i32]) -> Vec<usize> {
let mut queue = VecDeque::new();
let mut result = Vec::new();
for (i, °) in indegree.iter().enumerate() {
if deg == 0 {
queue.push_back(i);
}
}
while let Some(node) = queue.pop_front() {
result.push(node);
for &neighbor in &graph[node] {
indegree[neighbor] -= 1;
if indegree[neighbor] == 0 {
queue.push_back(neighbor);
}
}
}
result
}
TypeScript
function sortItems(n: number, m: number, group: number[], beforeItems: number[][]): number[] {
function topologicalSort(graph: number[][], indegree: number[]): number[] {
const queue: number[] = [];
const result: number[] = [];
for (let i = 0; i < indegree.length; i++) {
if (indegree[i] === 0) {
queue.push(i);
}
}
while (queue.length > 0) {
const node = queue.shift()!;
result.push(node);
for (const neighbor of graph[node]) {
indegree[neighbor]--;
if (indegree[neighbor] === 0) {
queue.push(neighbor);
}
}
}
return result;
}
// Assign unique group IDs
let groupId = m;
for (let i = 0; i < n; i++) {
if (group[i] === -1) {
group[i] = groupId++;
}
}
// Build graphs
const groupGraph: number[][] = Array(groupId).fill(null).map(() => []);
const groupIndegree: number[] = Array(groupId).fill(0);
const itemGraph: number[][] = Array(n).fill(null).map(() => []);
const itemIndegree: number[] = Array(n).fill(0);
for (let i = 0; i < n; i++) {
for (const prev of beforeItems[i]) {
itemGraph[prev].push(i);
itemIndegree[i]++;
if (group[prev] !== group[i]) {
groupGraph[group[prev]].push(group[i]);
groupIndegree[group[i]]++;
}
}
}
// Topological sorts
const groupOrder = topologicalSort(groupGraph, [...groupIndegree]);
if (groupOrder.length !== groupId) return [];
const itemOrder = topologicalSort(itemGraph, [...itemIndegree]);
if (itemOrder.length !== n) return [];
// Group items
const groupToItems = new Map<number, number[]>();
for (const item of itemOrder) {
const g = group[item];
if (!groupToItems.has(g)) {
groupToItems.set(g, []);
}
groupToItems.get(g)!.push(item);
}
// Build result
const result: number[] = [];
for (const g of groupOrder) {
if (groupToItems.has(g)) {
result.push(...groupToItems.get(g)!);
}
}
return result;
}
Complexity
- ⏰ Time complexity:
O(V + E)where V is the total number of items and groups, E is the total number of dependencies - 🧺 Space complexity:
O(V + E)for storing graphs and dependency relationships