Sort items by groups respecting dependencies

Depth-First Search Breadth-First Search Graph Theory Topological Sort

65.6% acceptance

Feb 25, 2026

1906

320

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.

Solution

Rust

Time O(n * m)

Space O(n * m)

LeetCode

solution.rs

impl Solution {
  pub fn sort_items(n: i32, m: i32, group: Vec<i32>, before_items: Vec<Vec<i32>>) -> Vec<i32> {
    let n = n as usize;
    let mut m = m as usize;

    // Assign unique group IDs to ungrouped items
    let mut group = group;
    for i in 0..n {
      if group[i] == -1 {
        group[i] = m as i32;
        m += 1;
      }
    }

    // Build item graph and group graph
    let mut item_indegree = vec![0usize; n];
    let mut group_indegree = vec![0usize; m];
    let mut item_graph: Vec<Vec<usize>> = vec![vec![]; n];
    let mut group_graph: Vec<Vec<usize>> = vec![vec![]; m];

    for i in 0..n {
      for &pre in &before_items[i] {
        let pre = pre as usize;
        // item dependency
        item_graph[pre].push(i);
        item_indegree[i] += 1;
        // group dependency
        let gi = group[i] as usize;
        let gpre = group[pre] as usize;
        if gi != gpre {
          group_graph[gpre].push(gi);
          group_indegree[gi] += 1;
        }
      }
    }

    // Deduplicate group graph
    for i in 0..m {
      group_graph[i].sort();
      group_graph[i].dedup();
    }
    // Recalculate group indegrees after dedup
    let mut group_indegree = vec![0usize; m];
    for i in 0..m {
      for &j in &group_graph[i] {
        group_indegree[j] += 1;
      }
    }

    fn topo_sort(graph: &Vec<Vec<usize>>, indegree: &Vec<usize>, size: usize) -> Option<Vec<usize>> {
      let mut indegree = indegree.clone();
      let mut queue: std::collections::VecDeque<usize> = (0..size).filter(|&i| indegree[i] == 0).collect();
      let mut result = vec![];
      while let Some(node) = queue.pop_front() {
        result.push(node);
        for &next in &graph[node] {
          indegree[next] -= 1;
          if indegree[next] == 0 {
            queue.push_back(next);
          }
        }
      }
      if result.len() == size { Some(result) } else { None }
    }

    let item_order = match topo_sort(&item_graph, &item_indegree, n) {
      Some(o) => o,
      None => return vec![],
    };
    let group_order = match topo_sort(&group_graph, &group_indegree, m) {
      Some(o) => o,
      None => return vec![],
    };

    // Group items by their group
    let mut group_items: Vec<Vec<usize>> = vec![vec![]; m];
    for &item in &item_order {
      group_items[group[item] as usize].push(item);
    }

    let mut result = vec![];
    for g in group_order {
      result.extend(group_items[g].iter().map(|&x| x as i32));
    }
    result
  }
}