Sort Items by Groups Respecting Dependencies

Problem#

n items belong to groups. Each item has prerequisites. Return any ordering of items such that (a) all items in the same group are contiguous and (b) all prerequisites come before their dependents. -1 if impossible.

Hints#

Hint 1

Two nested topological sorts: one on groups, one on items within each group, with cross-group prereqs creating group-level edges.

Approach#

Assign items without a group their own unique group ID. Build two graphs: item-level (within-group edges and ignored cross-group), and group-level (cross-group edges). Topo-sort groups; within each group’s items, topo-sort. Concatenate.

Solution#

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        for (int i = 0; i < n; ++i) if (group[i] == -1) group[i] = m++;
        vector<vector<int>> itemAdj(n), grpAdj(m);
        vector<int> itemIn(n, 0), grpIn(m, 0);
        for (int i = 0; i < n; ++i) for (int p : beforeItems[i]) {
            if (group[i] == group[p]) {
                itemAdj[p].push_back(i);
                ++itemIn[i];
            } else {
                grpAdj[group[p]].push_back(group[i]);
                ++grpIn[group[i]];
            }
        }
        auto topo = [](int n, vector<vector<int>>& adj, vector<int>& indeg) {
            queue<int> q;
            for (int i = 0; i < n; ++i) if (indeg[i] == 0) q.push(i);
            vector<int> out;
            while (!q.empty()) {
                int u = q.front(); q.pop();
                out.push_back(u);
                for (int v : adj[u]) if (--indeg[v] == 0) q.push(v);
            }
            return (int)out.size() == n ? out : vector<int>{};
        };
        auto grpOrder = topo(m, grpAdj, grpIn);
        auto itemOrder = topo(n, itemAdj, itemIn);
        if (grpOrder.empty() || itemOrder.empty()) return {};
        unordered_map<int, vector<int>> itemsByGroup;
        for (int it : itemOrder) itemsByGroup[group[it]].push_back(it);
        vector<int> ans;
        for (int g : grpOrder) for (int it : itemsByGroup[g]) ans.push_back(it);
        return ans;
    }
};

func sortItems(n int, m int, group []int, beforeItems [][]int) []int {
    for i := 0; i < n; i++ {
        if group[i] == -1 {
            group[i] = m
            m++
        }
    }
    itemAdj := make([][]int, n)
    grpAdj := make([][]int, m)
    itemIn := make([]int, n)
    grpIn := make([]int, m)
    for i := 0; i < n; i++ {
        for _, p := range beforeItems[i] {
            if group[i] == group[p] {
                itemAdj[p] = append(itemAdj[p], i)
                itemIn[i]++
            } else {
                grpAdj[group[p]] = append(grpAdj[group[p]], group[i])
                grpIn[group[i]]++
            }
        }
    }
    topo := func(sz int, adj [][]int, indeg []int) []int {
        q := []int{}
        for i := 0; i < sz; i++ {
            if indeg[i] == 0 {
                q = append(q, i)
            }
        }
        out := []int{}
        for len(q) > 0 {
            u := q[0]
            q = q[1:]
            out = append(out, u)
            for _, v := range adj[u] {
                indeg[v]--
                if indeg[v] == 0 {
                    q = append(q, v)
                }
            }
        }
        if len(out) == sz {
            return out
        }
        return nil
    }
    grpOrder := topo(m, grpAdj, grpIn)
    itemOrder := topo(n, itemAdj, itemIn)
    if grpOrder == nil || itemOrder == nil {
        return []int{}
    }
    itemsByGroup := map[int][]int{}
    for _, it := range itemOrder {
        itemsByGroup[group[it]] = append(itemsByGroup[group[it]], it)
    }
    ans := []int{}
    for _, g := range grpOrder {
        for _, it := range itemsByGroup[g] {
            ans = append(ans, it)
        }
    }
    return ans
}

from collections import defaultdict, deque
from typing import List

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        for i in range(n):
            if group[i] == -1:
                group[i] = m
                m += 1
        item_adj = [[] for _ in range(n)]
        grp_adj = [[] for _ in range(m)]
        item_in = [0] * n
        grp_in = [0] * m
        for i in range(n):
            for p in beforeItems[i]:
                if group[i] == group[p]:
                    item_adj[p].append(i)
                    item_in[i] += 1
                else:
                    grp_adj[group[p]].append(group[i])
                    grp_in[group[i]] += 1

        def topo(sz: int, adj: List[List[int]], indeg: List[int]) -> List[int]:
            q = deque(i for i in range(sz) if indeg[i] == 0)
            out = []
            while q:
                u = q.popleft()
                out.append(u)
                for v in adj[u]:
                    indeg[v] -= 1
                    if indeg[v] == 0:
                        q.append(v)
            return out if len(out) == sz else []

        grp_order = topo(m, grp_adj, grp_in)
        item_order = topo(n, item_adj, item_in)
        if not grp_order or not item_order:
            return []
        items_by_group = defaultdict(list)
        for it in item_order:
            items_by_group[group[it]].append(it)
        ans = []
        for g in grp_order:
            ans.extend(items_by_group[g])
        return ans

function sortItems(n, m, group, beforeItems) {
    for (let i = 0; i < n; i++) {
        if (group[i] === -1) group[i] = m++;
    }
    const itemAdj = Array.from({ length: n }, () => []);
    const grpAdj = Array.from({ length: m }, () => []);
    const itemIn = new Array(n).fill(0);
    const grpIn = new Array(m).fill(0);
    for (let i = 0; i < n; i++) {
        for (const p of beforeItems[i]) {
            if (group[i] === group[p]) {
                itemAdj[p].push(i);
                itemIn[i]++;
            } else {
                grpAdj[group[p]].push(group[i]);
                grpIn[group[i]]++;
            }
        }
    }
    const topo = (sz, adj, indeg) => {
        const q = [];
        for (let i = 0; i < sz; i++) if (indeg[i] === 0) q.push(i);
        const out = [];
        let head = 0;
        while (head < q.length) {
            const u = q[head++];
            out.push(u);
            for (const v of adj[u]) {
                if (--indeg[v] === 0) q.push(v);
            }
        }
        return out.length === sz ? out : [];
    };
    const grpOrder = topo(m, grpAdj, grpIn);
    const itemOrder = topo(n, itemAdj, itemIn);
    if (!grpOrder.length || !itemOrder.length) return [];
    const itemsByGroup = new Map();
    for (const it of itemOrder) {
        if (!itemsByGroup.has(group[it])) itemsByGroup.set(group[it], []);
        itemsByGroup.get(group[it]).push(it);
    }
    const ans = [];
    for (const g of grpOrder) {
        const items = itemsByGroup.get(g);
        if (items) for (const it of items) ans.push(it);
    }
    return ans;
}

class Solution {
    private List<Integer> topo(int sz, List<List<Integer>> adj, int[] indeg) {
        Deque<Integer> q = new ArrayDeque<>();
        for (int i = 0; i < sz; i++) if (indeg[i] == 0) q.offer(i);
        List<Integer> out = new ArrayList<>();
        while (!q.isEmpty()) {
            int u = q.poll();
            out.add(u);
            for (int v : adj.get(u)) {
                if (--indeg[v] == 0) q.offer(v);
            }
        }
        return out.size() == sz ? out : new ArrayList<>();
    }

    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        for (int i = 0; i < n; i++) if (group[i] == -1) group[i] = m++;
        List<List<Integer>> itemAdj = new ArrayList<>();
        List<List<Integer>> grpAdj = new ArrayList<>();
        for (int i = 0; i < n; i++) itemAdj.add(new ArrayList<>());
        for (int i = 0; i < m; i++) grpAdj.add(new ArrayList<>());
        int[] itemIn = new int[n];
        int[] grpIn = new int[m];
        for (int i = 0; i < n; i++) {
            for (int p : beforeItems.get(i)) {
                if (group[i] == group[p]) {
                    itemAdj.get(p).add(i);
                    itemIn[i]++;
                } else {
                    grpAdj.get(group[p]).add(group[i]);
                    grpIn[group[i]]++;
                }
            }
        }
        List<Integer> grpOrder = topo(m, grpAdj, grpIn);
        List<Integer> itemOrder = topo(n, itemAdj, itemIn);
        if (grpOrder.isEmpty() || itemOrder.isEmpty()) return new int[0];
        Map<Integer, List<Integer>> itemsByGroup = new HashMap<>();
        for (int it : itemOrder) {
            itemsByGroup.computeIfAbsent(group[it], k -> new ArrayList<>()).add(it);
        }
        int[] ans = new int[n];
        int idx = 0;
        for (int g : grpOrder) {
            List<Integer> items = itemsByGroup.get(g);
            if (items != null) for (int it : items) ans[idx++] = it;
        }
        return ans;
    }
}

function sortItems(n: number, m: number, group: number[], beforeItems: number[][]): number[] {
    for (let i = 0; i < n; i++) {
        if (group[i] === -1) group[i] = m++;
    }
    const itemAdj: number[][] = Array.from({ length: n }, () => []);
    const grpAdj: number[][] = Array.from({ length: m }, () => []);
    const itemIn: number[] = new Array(n).fill(0);
    const grpIn: number[] = new Array(m).fill(0);
    for (let i = 0; i < n; i++) {
        for (const p of beforeItems[i]) {
            if (group[i] === group[p]) {
                itemAdj[p].push(i);
                itemIn[i]++;
            } else {
                grpAdj[group[p]].push(group[i]);
                grpIn[group[i]]++;
            }
        }
    }
    const topo = (sz: number, adj: number[][], indeg: number[]): number[] => {
        const q: number[] = [];
        for (let i = 0; i < sz; i++) if (indeg[i] === 0) q.push(i);
        const out: number[] = [];
        let head = 0;
        while (head < q.length) {
            const u = q[head++];
            out.push(u);
            for (const v of adj[u]) {
                if (--indeg[v] === 0) q.push(v);
            }
        }
        return out.length === sz ? out : [];
    };
    const grpOrder = topo(m, grpAdj, grpIn);
    const itemOrder = topo(n, itemAdj, itemIn);
    if (!grpOrder.length || !itemOrder.length) return [];
    const itemsByGroup = new Map<number, number[]>();
    for (const it of itemOrder) {
        if (!itemsByGroup.has(group[it])) itemsByGroup.set(group[it], []);
        itemsByGroup.get(group[it])!.push(it);
    }
    const ans: number[] = [];
    for (const g of grpOrder) {
        const items = itemsByGroup.get(g);
        if (items) for (const it of items) ans.push(it);
    }
    return ans;
}

Editorial#

Two-level topo sort cleanly separates concerns: groups order across teams; items order within each team. Cross-group prereqs constrain group ordering; same-group prereqs constrain item ordering. Each topo independently runs Kahn’s.

Complexity#

Time: O(V + E).
Space: O(V + E).

Problem#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Keyboard shortcuts

Problem#

Hints#

Approach#

Solution#

Editorial#

Complexity#

Concept revision#

Related#