Demo preview: These solutions pass the automated test suite but have not been human-reviewed. Treat trade-offs and prose as draft.

Sort Items by Groups Respecting Dependencies

Problem (restated)

n items, some in groups (group[i] or -1 free). beforeItems[i] lists prerequisites. Return a valid order where group members are contiguous and prereqs hold, or empty if impossible.

Intuition

Assign free items unique groups. Topo-sort groups using cross-group edges; topo-sort items for relative order; emit each group’s members in global item order.

Approaches

Dual topological sort (groups + items)

Unverified

Time O(n + e)Space O(n + e)

Idea. Two graphs: item-level and group-level. Cycle in either → []. Validate final indices against beforeItems.

Walkthrough. Small n with two groups and cross edges forces group block order then items inside.

Trade-offs. Contiguity is enforced by emitting whole group blocks from group topo order.

Solution

export function sortItems(
  n: number,
  m: number,
  group: number[],
  beforeItems: number[][],
): number[] {
  group = [...group];
  let gid = m;
  for (let i = 0; i < n; i++) if (group[i] === -1) group[i] = gid++;
  const gCount = gid;
  const itemG: number[][] = Array.from({ length: n }, () => []);
  const itemIndeg = Array(n).fill(0);
  const groupEdgeSet = new Set<string>();
  for (let v = 0; v < n; v++) {
    for (const u of beforeItems[v]!) {
      itemG[u]!.push(v);
      itemIndeg[v]!++;
      if (group[u] !== group[v]) groupEdgeSet.add(`${group[u]},${group[v]}`);
    }
  }
  const groupG: number[][] = Array.from({ length: gCount }, () => []);
  const groupIndeg = Array(gCount).fill(0);
  for (const key of groupEdgeSet) {
    const [a, b] = key.split(",").map(Number) as [number, number];
    groupG[a]!.push(b);
    groupIndeg[b]!++;
  }
  const kahn = (graph: number[][], indeg: number[], nodes: number[]): number[] | null => {
    const local = [...indeg];
    const set = new Set(nodes);
    const q = nodes.filter((u) => local[u] === 0);
    const order: number[] = [];
    while (q.length) {
      const u = q.shift()!;
      order.push(u);
      for (const v of graph[u]!) {
        if (!set.has(v)) continue;
        if (--local[v]! === 0) q.push(v);
      }
    }
    return order.length === nodes.length ? order : null;
  };
  const groupOrder = kahn(groupG, groupIndeg, [...Array(gCount).keys()]);
  if (!groupOrder) return [];
  const itemOrder = kahn(itemG, itemIndeg, [...Array(n).keys()]);
  if (!itemOrder) return [];
  const pos = new Map(itemOrder.map((x, i) => [x, i]));
  const members: number[][] = Array.from({ length: gCount }, () => []);
  for (let i = 0; i < n; i++) members[group[i]!]!.push(i);
  const res: number[] = [];
  for (const gr of groupOrder) {
    const mem = [...members[gr]!].sort((a, b) => pos.get(a)! - pos.get(b)!);
    res.push(...mem);
  }
  const idx = new Map(res.map((x, i) => [x, i]));
  for (let v = 0; v < n; v++) {
    for (const u of beforeItems[v]!) {
      if (idx.get(u)! >= idx.get(v)!) return [];
    }
  }
  return res;
}

export function sortItems(
  n: number,
  m: number,
  group: number[],
  beforeItems: number[][],
): number[] {
  group = [...group];
  let gid = m;
  for (let i = 0; i < n; i++) if (group[i] === -1) group[i] = gid++;
  const gCount = gid;
  const itemG: number[][] = Array.from({ length: n }, () => []);
  const itemIndeg = Array(n).fill(0);
  const groupEdgeSet = new Set<string>();
  for (let v = 0; v < n; v++) {
    for (const u of beforeItems[v]!) {
      itemG[u]!.push(v);
      itemIndeg[v]!++;
      if (group[u] !== group[v]) groupEdgeSet.add(`${group[u]},${group[v]}`);
    }
  }
  const groupG: number[][] = Array.from({ length: gCount }, () => []);
  const groupIndeg = Array(gCount).fill(0);
  for (const key of groupEdgeSet) {
    const [a, b] = key.split(",").map(Number) as [number, number];
    groupG[a]!.push(b);
    groupIndeg[b]!++;
  }
  const kahn = (graph: number[][], indeg: number[], nodes: number[]): number[] | null => {
    const local = [...indeg];
    const set = new Set(nodes);
    const q = nodes.filter((u) => local[u] === 0);
    const order: number[] = [];
    while (q.length) {
      const u = q.shift()!;
      order.push(u);
      for (const v of graph[u]!) {
        if (!set.has(v)) continue;
        if (--local[v]! === 0) q.push(v);
      }
    }
    return order.length === nodes.length ? order : null;
  };
  const groupOrder = kahn(groupG, groupIndeg, [...Array(gCount).keys()]);
  if (!groupOrder) return [];
  const itemOrder = kahn(itemG, itemIndeg, [...Array(n).keys()]);
  if (!itemOrder) return [];
  const pos = new Map(itemOrder.map((x, i) => [x, i]));
  const members: number[][] = Array.from({ length: gCount }, () => []);
  for (let i = 0; i < n; i++) members[group[i]!]!.push(i);
  const res: number[] = [];
  for (const gr of groupOrder) {
    const mem = [...members[gr]!].sort((a, b) => pos.get(a)! - pos.get(b)!);
    res.push(...mem);
  }
  const idx = new Map(res.map((x, i) => [x, i]));
  for (let v = 0; v < n; v++) {
    for (const u of beforeItems[v]!) {
      if (idx.get(u)! >= idx.get(v)!) return [];
    }
  }
  return res;
}

Template connection

Topological sort applied at two hierarchy levels.

Reflection

Sort twice: groups against groups, then items inside a group. An item edge that crosses groups is also a group edge. A group id of −1 is its own group.
A cycle among groups or among items answers an empty list. Emit a whole group, then the items of that group.
No dependencies: any order is valid. If every item is in group −1, one Kahn runs inside that single group.