LeetCode 1203 - Sort Items by Groups Respecting Dependencies

LeetCode Problem 1203

Difficulty: 🔴 Hard
Topics: Depth-First Search, Breadth-First Search, Graph Theory, Topological Sort

Solution

Problem Understanding

This problem asks us to sort n items while satisfying two different kinds of constraints at the same time.

The first constraint comes from dependencies between items. If item a appears in beforeItems[b], then item a must appear before item b in the final ordering. This is a classic dependency ordering problem, which naturally suggests topological sorting on a directed graph.

The second constraint is about groups. Every item belongs to either exactly one group or no group at all. Items that belong to the same group must appear consecutively in the final answer. In other words, if a group contains items {2, 5, 7}, then those items must appear as one continuous block in the output. Other groups cannot be interleaved between them.

The input consists of:

• n, the number of items.
• m, the initial number of groups.
• group[i], which tells us which group item i belongs to. If group[i] == -1, the item initially belongs to no group.
• beforeItems[i], a list of items that must come before item i.

The output should be a valid ordering of all items that satisfies:

1. All dependency constraints.
2. All same-group adjacency constraints.

If no such ordering exists, we must return an empty list.

The constraints are large:

• n can be as large as 3 * 10^4
• The dependency graph can contain many edges

This immediately rules out exponential or brute-force permutation generation approaches. We need an algorithm close to linear time, ideally proportional to the number of items plus the number of dependency edges.

One subtle aspect of the problem is how to handle items with group[i] == -1. Since every group must appear as a contiguous block, ungrouped items cannot simply float freely. The standard trick is to assign every ungrouped item its own unique group. This converts the problem into one where every item belongs to exactly one group.

Several edge cases are important:

• Cycles between items make the ordering impossible.
• Cycles between groups also make the ordering impossible.
• Groups may contain only one item.
• Some groups may contain no items at all.
• Dependencies may exist both inside the same group and across different groups.
• Multiple valid answers may exist.

The core challenge is combining topological sorting with grouping constraints in a clean and efficient way.

Approaches

Brute Force Approach

A brute-force solution would generate all possible permutations of the items and check whether each permutation satisfies both conditions:

1. Dependency constraints.
2. Group contiguity constraints.

For every permutation, we would verify:

• For each dependency u -> v, item u appears before v.
• All items of the same group appear together.

This approach is correct because it exhaustively checks every possible ordering and returns one that satisfies all constraints.

However, the number of permutations is n!, which becomes impossibly large even for moderate values of n. Since n can be up to 30000, brute force is completely infeasible.

Optimal Approach

The key insight is that the problem actually contains two levels of ordering:

1. Ordering between groups.
2. Ordering between items inside each group.

We can model both levels as directed graphs.

First, we assign unique groups to all ungrouped items. Then:

• Build an item dependency graph.
• Build a group dependency graph.

If item u must come before item v:

• If they belong to the same group, this becomes an edge inside the item graph.
• If they belong to different groups, this also creates a dependency between the two groups.

We then perform two separate topological sorts:

1. Topologically sort the groups.
2. Topologically sort the items.

Once we know the item order, we can collect items by group while preserving their internal order. Then we output groups according to the group topological order.

This works because:

• Group topological order guarantees valid inter-group dependencies.
• Item topological order guarantees valid intra-group dependencies.
• Grouped output guarantees contiguous group blocks.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n!)	O(n!)	Generates all permutations
Optimal	O(n + e)	O(n + e)	Uses dual topological sorting

Here, e is the total number of dependency edges.

Algorithm Walkthrough

1. Assign unique groups to ungrouped items.

Any item with group[i] == -1 gets assigned a new unique group ID starting from m.

This simplifies the problem because every item now belongs to exactly one group. 2. Build the item graph.

Create:

• An adjacency list for item dependencies.
• An indegree array for items.

For every dependency prev -> curr:

• Add an edge from prev to curr.
• Increment curr's indegree.

3. Build the group graph.

If two dependent items belong to different groups:

• Add an edge from group[prev] to group[curr].
• Increment the indegree of group[curr].

We use a set to avoid duplicate group edges. 4. Perform topological sort on items.

Use Kahn's Algorithm:

• Start with all items having indegree 0.
• Repeatedly remove nodes from the queue.
• Reduce indegrees of neighbors.
• Add new zero-indegree nodes to the queue.

If we cannot process all items, there is a cycle, so return an empty list. 5. Perform topological sort on groups.

Repeat the same process for groups.

If not all groups can be processed, there is a cycle between groups, so return an empty list. 6. Group items according to item order.

Traverse the topologically sorted item list.

For each item:

• Append it to a list associated with its group.

Because items are processed in valid dependency order, each group list preserves valid internal ordering. 7. Build the final answer.

Traverse groups in topological order.

For each group:

• Append all items belonging to that group.

This guarantees:

• Group contiguity.
• Valid dependency order.

Why it works

The algorithm separates global ordering from local ordering.

The group topological sort guarantees that all dependencies crossing group boundaries are respected. The item topological sort guarantees that all item-level dependencies are respected. Since items are collected group-by-group while preserving item topological order, every dependency remains valid and all items from the same group appear consecutively.

If either graph contains a cycle, no valid ordering exists, and the algorithm correctly returns an empty list.

Python Solution

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]:

        # Assign unique groups to ungrouped items
        next_group_id = m

        for item in range(n):
            if group[item] == -1:
                group[item] = next_group_id
                next_group_id += 1

        total_groups = next_group_id

        # Graphs and indegrees
        item_graph = defaultdict(list)
        item_indegree = [0] * n

        group_graph = defaultdict(list)
        group_indegree = [0] * total_groups

        # Avoid duplicate group edges
        group_edges = set()

        # Build graphs
        for curr in range(n):
            for prev in beforeItems[curr]:

                # Item graph
                item_graph[prev].append(curr)
                item_indegree[curr] += 1

                prev_group = group[prev]
                curr_group = group[curr]

                # Group graph
                if prev_group != curr_group:
                    edge = (prev_group, curr_group)

                    if edge not in group_edges:
                        group_edges.add(edge)
                        group_graph[prev_group].append(curr_group)
                        group_indegree[curr_group] += 1

        def topological_sort(nodes: List[int], graph, indegree):
            queue = deque()

            for node in nodes:
                if indegree[node] == 0:
                    queue.append(node)

            order = []

            while queue:
                node = queue.popleft()
                order.append(node)

                for neighbor in graph[node]:
                    indegree[neighbor] -= 1

                    if indegree[neighbor] == 0:
                        queue.append(neighbor)

            if len(order) != len(nodes):
                return []

            return order

        # Topological sort items
        item_order = topological_sort(
            list(range(n)),
            item_graph,
            item_indegree[:]
        )

        if not item_order:
            return []

        # Topological sort groups
        group_order = topological_sort(
            list(range(total_groups)),
            group_graph,
            group_indegree[:]
        )

        if not group_order:
            return []

        # Group items according to item order
        ordered_group_items = defaultdict(list)

        for item in item_order:
            ordered_group_items[group[item]].append(item)

        # Build final result
        result = []

        for grp in group_order:
            result.extend(ordered_group_items[grp])

        return result

The implementation starts by assigning unique group IDs to all ungrouped items. This transforms the problem into a cleaner structure where every item belongs to exactly one group.

Next, two graphs are built. The item graph captures direct dependencies between items, while the group graph captures dependencies between groups. The group graph only receives edges when dependencies cross group boundaries.

The topological_sort helper function implements Kahn's Algorithm. It processes all zero-indegree nodes first and gradually removes dependencies from the graph. If some nodes remain unprocessed, a cycle exists.

The item topological sort ensures all item dependencies are satisfied. The group topological sort ensures groups appear in a valid global order.

Finally, items are grouped according to their topological item order, and groups are emitted according to the topological group order.

Go Solution

package main

func sortItems(n int, m int, group []int, beforeItems [][]int) []int {

	// Assign unique groups to ungrouped items
	nextGroupID := m

	for i := 0; i < n; i++ {
		if group[i] == -1 {
			group[i] = nextGroupID
			nextGroupID++
		}
	}

	totalGroups := nextGroupID

	// Item graph
	itemGraph := make([][]int, n)
	itemIndegree := make([]int, n)

	// Group graph
	groupGraph := make([][]int, totalGroups)
	groupIndegree := make([]int, totalGroups)

	// Avoid duplicate group edges
	groupEdges := make(map[[2]int]bool)

	// Build graphs
	for curr := 0; curr < n; curr++ {
		for _, prev := range beforeItems[curr] {

			// Item graph
			itemGraph[prev] = append(itemGraph[prev], curr)
			itemIndegree[curr]++

			prevGroup := group[prev]
			currGroup := group[curr]

			// Group graph
			if prevGroup != currGroup {
				edge := [2]int{prevGroup, currGroup}

				if !groupEdges[edge] {
					groupEdges[edge] = true
					groupGraph[prevGroup] = append(groupGraph[prevGroup], currGroup)
					groupIndegree[currGroup]++
				}
			}
		}
	}

	topologicalSort := func(nodes []int, graph [][]int, indegree []int) []int {

		queue := make([]int, 0)

		for _, node := range nodes {
			if indegree[node] == 0 {
				queue = append(queue, node)
			}
		}

		order := make([]int, 0)
		head := 0

		for head < len(queue) {
			node := queue[head]
			head++

			order = append(order, node)

			for _, neighbor := range graph[node] {
				indegree[neighbor]--

				if indegree[neighbor] == 0 {
					queue = append(queue, neighbor)
				}
			}
		}

		if len(order) != len(nodes) {
			return []int{}
		}

		return order
	}

	// Topological sort items
	itemNodes := make([]int, n)

	for i := 0; i < n; i++ {
		itemNodes[i] = i
	}

	itemOrder := topologicalSort(itemNodes, itemGraph, append([]int(nil), itemIndegree...))

	if len(itemOrder) == 0 {
		return []int{}
	}

	// Topological sort groups
	groupNodes := make([]int, totalGroups)

	for i := 0; i < totalGroups; i++ {
		groupNodes[i] = i
	}

	groupOrder := topologicalSort(groupNodes, groupGraph, append([]int(nil), groupIndegree...))

	if len(groupOrder) == 0 {
		return []int{}
	}

	// Collect items by group
	groupedItems := make(map[int][]int)

	for _, item := range itemOrder {
		grp := group[item]
		groupedItems[grp] = append(groupedItems[grp], item)
	}

	// Build final result
	result := make([]int, 0)

	for _, grp := range groupOrder {
		result = append(result, groupedItems[grp]...)
	}

	return result
}

The Go implementation follows the same algorithmic structure as the Python version, but uses slices and maps instead of Python collections.

One important detail is copying indegree arrays before topological sorting. Since Kahn's Algorithm mutates indegrees, we use:

append([]int(nil), itemIndegree...)

to create a copy.

The queue is implemented using a slice with a moving head pointer, which avoids inefficient front removals.

Go slices naturally handle empty groups because appending a nil slice is safe.

Worked Examples

Example 1

n = 8
m = 2

group = [-1,-1,1,0,0,1,0,-1]

beforeItems =
[
  [],
  [6],
  [5],
  [6],
  [3,6],
  [],
  [],
  []
]

Step 1: Assign Unique Groups

Ungrouped items are:

• item 0
• item 1
• item 7

Assign new groups:

Item	New Group
0	2
1	3
7	4

Updated groups:

group = [2,3,1,0,0,1,0,4]

Step 2: Build Item Graph

Dependencies:

Dependency	Edge
6 before 1	6 -> 1
5 before 2	5 -> 2
6 before 3	6 -> 3
3 before 4	3 -> 4
6 before 4	6 -> 4

Item indegrees:

Item	Indegree
0	0
1	1
2	1
3	1
4	2
5	0
6	0
7	0

Step 3: Build Group Graph

Cross-group dependencies:

Item Edge	Group Edge
6 -> 1	0 -> 3
5 -> 2	same group
6 -> 3	same group
3 -> 4	same group
6 -> 4	same group

Group graph:

0 -> 3

Step 4: Topological Sort Items

Initial queue:

[0,5,6,7]

Processing order evolves:

Processed	New Queue
0	[5,6,7]
5	[6,7,2]
6	[7,2,1,3]
7	[2,1,3]
2	[1,3]
1	[3]
3	[4]
4	[]

Item order:

[0,5,6,7,2,1,3,4]

Step 5: Topological Sort Groups

Possible group order:

[0,1,2,4,3]

Step 6: Collect Items by Group

Group	Items
0	[6,3,4]
1	[5,2]
2	[0]
3	[1]
4	[7]

Step 7: Build Final Result

Final ordering:

[6,3,4,5,2,0,7,1]

This satisfies:

• All dependencies
• Group contiguity

Example 2

Additional dependency:

4 -> 6

Now we have:

6 -> 3 -> 4 -> 6

This creates a cycle.

During topological sorting:

• Some nodes never reach indegree 0
• Not all items are processed

Therefore, the algorithm correctly returns:

[]

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n + e)	Each node and edge is processed a constant number of times
Space	O(n + e)	Graphs, indegree arrays, and queues require linear storage

Here:

• n is the number of items
• e is the total number of dependency edges

The algorithm is efficient because Kahn's Algorithm processes every node once and every edge once. Building both graphs is also linear in the number of dependencies.

Even with two separate topological sorts, the total runtime remains linear.

Test Cases

from typing import List

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        from collections import defaultdict, deque

        next_group_id = m

        for i in range(n):
            if group[i] == -1:
                group[i] = next_group_id
                next_group_id += 1

        total_groups = next_group_id

        item_graph = defaultdict(list)
        item_indegree = [0] * n

        group_graph = defaultdict(list)
        group_indegree = [0] * total_groups

        group_edges = set()

        for curr in range(n):
            for prev in beforeItems[curr]:

                item_graph[prev].append(curr)
                item_indegree[curr] += 1

                g1 = group[prev]
                g2 = group[curr]

                if g1 != g2:
                    edge = (g1, g2)

                    if edge not in group_edges:
                        group_edges.add(edge)
                        group_graph[g1].append(g2)
                        group_indegree[g2] += 1

        def topo(nodes, graph, indegree):
            q = deque()

            for node in nodes:
                if indegree[node] == 0:
                    q.append(node)

            order = []

            while q:
                node = q.popleft()
                order.append(node)

                for nei in graph[node]:
                    indegree[nei] -= 1

                    if indegree[nei] == 0:
                        q.append(nei)

            return order if len(order) == len(nodes) else []

        item_order = topo(list(range(n)), item_graph, item_indegree[:])

        if not item_order:
            return []

        group_order = topo(list(range(total_groups)), group_graph, group_indegree[:])

        if not group_order:
            return []

        grouped = defaultdict(list)

        for item in item_order:
            grouped[group[item]].append(item)

        result = []

        for grp in group_order:
            result.extend(grouped[grp])

        return result

sol = Solution()

# Example 1
result = sol.sortItems(
    8,
    2,
    [-1,-1,1,0,0,1,0,-1],
    [[],[6],[5],[6],[3,6],[],[],[]]
)
assert len(result) == 8  # valid ordering exists

# Example 2
assert sol.sortItems(
    8,
    2,
    [-1,-1,1,0,0,1,0,-1],
    [[],[6],[5],[6],[3],[],[4],[]]
) == []  # cycle exists

# Single item
assert sol.sortItems(
    1,
    1,
    [0],
    [[]]
) == [0]  # smallest possible input

# No dependencies
result = sol.sortItems(
    4,
    2,
    [0,0,1,1],
    [[],[],[],[]]
)
assert len(result) == 4  # any grouped ordering is valid

# All items ungrouped
result = sol.sortItems(
    4,
    0,
    [-1,-1,-1,-1],
    [[],[0],[1],[2]]
)
assert result == [0,1,2,3]  # linear dependency chain

# Cycle inside one group
assert sol.sortItems(
    3,
    1,
    [0,0,0],
    [[2],[0],[1]]
) == []  # item-level cycle

# Cross-group dependencies
result = sol.sortItems(
    6,
    2,
    [0,0,0,1,1,1],
    [[],[],[],[0],[1],[2]]
)
assert len(result) == 6  # valid group ordering required

# Empty groups present
result = sol.sortItems(
    3,
    5,
    [0,2,4],
    [[],[],[]]
)
assert len(result) == 3  # groups with no items handled correctly

Test	Why
Example 1	Valid complex dependency graph
Example 2	Detects cycle correctly
Single item	Minimum input size
No dependencies	Verifies grouping behavior
All items ungrouped	Tests dynamic group assignment
Cycle inside one group	Detects item-level cycles
Cross-group dependencies	Verifies group topological ordering
Empty groups present	Ensures unused groups do not break logic

Edge Cases

Cycles Between Items

One of the most important edge cases is a dependency cycle between items. For example:

0 -> 1 -> 2 -> 0

In this situation, no valid ordering exists because every item depends on another item in the cycle. A naive implementation might loop forever or produce an invalid partial ordering.

The implementation handles this by checking whether the topological sort processes all nodes. If some nodes remain unprocessed, a cycle exists, and the algorithm returns an empty list.

Ungrouped Items

Items with group[i] == -1 can easily introduce bugs if not handled carefully. Since all items of a group must remain contiguous, leaving items ungrouped creates ambiguity.

The implementation solves this by assigning each ungrouped item a unique artificial group. This converts the problem into a uniform structure where every item belongs to exactly one group.

Duplicate Group Dependencies

Suppose multiple item dependencies create the same group dependency:

item 1 -> item 5
item 2 -> item 6

If both dependencies correspond to:

group 0 -> group 1

then adding duplicate edges repeatedly would incorrectly inflate indegrees and break the topological sort.

The implementation avoids this by storing group edges in a set before inserting them into the graph.

Empty Groups

Some groups may contain no items at all. A careless implementation might assume every group contributes items to the result.

The current solution safely handles empty groups because extending the result with an empty list has no effect. The topological sort still processes those groups correctly.

Independent Components

The dependency graph may contain completely disconnected components. For example:

0 -> 1

2 -> 3

Multiple valid topological orderings exist in this case.

Kahn's Algorithm naturally handles this by starting with all zero-indegree nodes, allowing independent components to be processed in any valid order.