Sort Items by Groups Respecting Dependencies

HardGraphs · Two-Level Topological Sort🧩 Topological Sort LeetCode #1203 ↗Updated Oct 30, 2026

Problem

There are n items and m groups. group[i] is the group of item i, or -1 if it belongs to none. beforeItems[i] lists items that must appear before item i. Return any ordering of all items that respects every dependency and keeps the items of each group next to each other; return an empty array if none exists.

Inputn=4, m=1, group=[-1,0,0,-1], before=[[],[0],[1],[2]]Output[0,1,2,3]

Inputn=3, m=1, group=[0,-1,0], before=[[],[0],[1]]Output[] (item 1 would split group 0)

Inputn=3, m=0, group=[-1,-1,-1], before=[[],[],[]]Outputany permutation, e.g. [0,1,2]

1 ≤ m ≤ n ≤ 3·10⁴ · -1 ≤ group[i] ≤ m-1 · 0 ≤ beforeItems[i].length ≤ n-1 · no self or duplicate dependencies

Try it yourself

Java

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        
    }
}

Your code is saved in this browser.Submit on LeetCode ↗

Key insight

Split it into two independent ordering problems: a topological order of the groups (a dependency between items of different groups is an edge between their groups) and a topological order of the items. Give each ungrouped item its own private group, then list groups in order, each with its items in item order.

PatternTopological Sort

Instinct Tasks with prerequisites, "X must come before Y", or an order hidden in comparisons: build a directed graph and peel off nodes with zero in-degree.

Memory hack No prereqs? Off you go. Each finished task frees its followers; if someone is never freed, there is a cycle.

Open the Topological Sort guide →

Approaches

Brute ForceBacktracking With a “Finish Your Group” Rule

Time O(2ⁿ·n·(n + m))Space O(2ⁿ·(n + m))

Build the order one item at a time: an item is eligible if all its prerequisites are placed. To keep groups contiguous, once we place an item of a group that still has unplaced items, the next item must come from that same group. Dead states (placed set, open group) are memoised.

Java

private int n, totalGroups;
private int[] grp, needMask, remaining, order;
private Set<Long> dead;

public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
    this.n = n;
    grp = group.clone();
    totalGroups = m;
    for (int i = 0; i < n; i++) if (grp[i] == -1) grp[i] = totalGroups++;
    remaining = new int[totalGroups];
    needMask = new int[n]; // bitmask of prerequisites (tiny n only)
    for (int i = 0; i < n; i++) {
        remaining[grp[i]]++;
        for (int p : beforeItems.get(i)) needMask[i] |= 1 << p;
    }
    dead = new HashSet<>();
    order = new int[n];
    return place(0, 0, -1) ? order : new int[0];
}

// open = group that must be continued next, or -1 if any eligible item may follow
private boolean place(int mask, int pos, int open) {
    if (pos == n) return true;
    long key = (long) mask * (totalGroups + 1) + (open + 1);
    if (dead.contains(key)) return false;
    for (int i = 0; i < n; i++) {
        if ((mask >> i & 1) == 1 || (needMask[i] & ~mask) != 0) continue;
        if (open != -1 && grp[i] != open) continue;
        order[pos] = i;
        remaining[grp[i]]--;
        int next = remaining[grp[i]] > 0 ? grp[i] : -1;
        boolean ok = place(mask | 1 << i, pos + 1, next);
        remaining[grp[i]]++;
        if (ok) return true;
    }
    dead.add(key);
    return false;
}

Exponential — only workable for tiny n, but a handy checker for small cases.

OptimalTwo-Level Kahn's Algorithm

Time O(n + m + E)Space O(n + m + E)

Map every -1 item to a fresh group id. Every dependency p → i is an item edge; if p and i are in different groups it is also a group edge. Topologically sort both graphs (a cycle in either means no answer). Bucket items by group following the item order, then output buckets following the group order.

Java

public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
    int[] grp = group.clone();
    int groups = m;
    for (int i = 0; i < n; i++) if (grp[i] == -1) grp[i] = groups++; // private group
    List<List<Integer>> itemAdj = emptyLists(n), groupAdj = emptyLists(groups);
    int[] itemIn = new int[n], groupIn = new int[groups];
    for (int i = 0; i < n; i++) {
        for (int p : beforeItems.get(i)) {
            itemAdj.get(p).add(i);
            itemIn[i]++;
            if (grp[p] != grp[i]) {
                groupAdj.get(grp[p]).add(grp[i]);
                groupIn[grp[i]]++;
            }
        }
    }
    List<Integer> itemOrder = topoSort(itemAdj, itemIn);
    List<Integer> groupOrder = topoSort(groupAdj, groupIn);
    if (itemOrder == null || groupOrder == null) return new int[0];
    List<List<Integer>> bucket = emptyLists(groups);
    for (int item : itemOrder) bucket.get(grp[item]).add(item);
    int[] result = new int[n];
    int k = 0;
    for (int g : groupOrder) {
        for (int item : bucket.get(g)) result[k++] = item;
    }
    return result;
}

// Kahn's algorithm; returns null if the graph has a cycle.
private List<Integer> topoSort(List<List<Integer>> adj, int[] indegree) {
    Deque<Integer> queue = new ArrayDeque<>();
    for (int v = 0; v < adj.size(); v++) if (indegree[v] == 0) queue.add(v);
    List<Integer> order = new ArrayList<>();
    while (!queue.isEmpty()) {
        int u = queue.poll();
        order.add(u);
        for (int v : adj.get(u)) if (--indegree[v] == 0) queue.add(v);
    }
    return order.size() == adj.size() ? order : null;
}

private List<List<Integer>> emptyLists(int size) {
    List<List<Integer>> lists = new ArrayList<>();
    for (int i = 0; i < size; i++) lists.add(new ArrayList<>());
    return lists;
}

Linear in the input size; each graph is a plain Kahn's run.

Pro tip

Duplicate group edges are harmless — each copy adds one to the in-degree and is removed once, so no de-duplication set is needed.

At a glance

Level	Approach	Time	Space
Brute Force	Backtracking With a “Finish Your Group” Rule	`O(2ⁿ·n·(n + m))`	`O(2ⁿ·(n + m))`
Optimal	Two-Level Kahn's Algorithm	`O(n + m + E)`	`O(n + m + E)`

Common pitfalls

Lumping all -1 items into one shared group — they must stay independent.
Sorting groups only — dependencies inside a group still need an item order.
Missing a group-level cycle that has no item-level cycle (A→B→A across items).

Interview tips

Say up front: “two topological sorts — one for groups, one for items”.
Explain why the bucketed item order still respects intra-group edges.
Factor Kahn's into one helper and call it twice; it keeps the code short and clear.

Pattern

Hierarchical topological sort → ordering with dependencies plus a “keep clusters together” constraint.

My notes saved in this browser