Problem: Sort Items by Groups Respecting Dependencies

Medium

30 min

Understand how to arrange items belonging to various groups while maintaining both dependency order and group continuity. This lesson teaches you to apply topological sort techniques to solve problems that require that all items in a group appear consecutively and after their prerequisites are ordered, preparing you for complex coding interview questions.

Statement

You are given $n$ items indexed from $0$ to $n − 1$ . Each item belongs to $0$ or one of m groups, described by the array group, where:

group[i] represents the group of the $i^{th}$ item.
If group[i] $==-1$ , the item isn’t assigned to any existing group and should be treated as belonging to its own unique group.

You’re also given a list, beforeItems, where beforeItems[i] contains all items that must precede item $i$ in the final ordering.

Your goal is to arrange all $n$ items in a list that satisfies both of the following rules:

Dependency order: Every item must appear after all the items listed in beforeItems[i].
Group continuity: All items that belong to the same group must appear next to each other in the final order.

If there are multiple valid orderings, return any of them. If there’s no possible ordering, return an empty list.

Constraints:

$1 \leq$ m $\leq$ n $\leq$ $3 \times 10^4$
group.length $==$ beforeItems.length $==$ n
$-1 \leq$ group[i] $\leq$ m - $1$
$0 \leq$ beforeItems[i].length $\leq$ n - $1$
$0 \leq$ beforeItems[i][j] $\leq$ n - $1$
i $!=$ beforeItems[i][j]
beforeItems[i] does not contain duplicate elements.

Problem: Sort Items by Groups Respecting Dependencies

Medium

30 min

Statement

You are given $n$ items indexed from $0$ to $n − 1$ . Each item belongs to $0$ or one of m groups, described by the array group, where:

group[i] represents the group of the $i^{th}$ item.
If group[i] $==-1$ , the item isn’t assigned to any existing group and should be treated as belonging to its own unique group.

You’re also given a list, beforeItems, where beforeItems[i] contains all items that must precede item $i$ in the final ordering.

Your goal is to arrange all $n$ items in a list that satisfies both of the following rules:

Dependency order: Every item must appear after all the items listed in beforeItems[i].
Group continuity: All items that belong to the same group must appear next to each other in the final order.

If there are multiple valid orderings, return any of them. If there’s no possible ordering, return an empty list.

Constraints:

$1 \leq$ m $\leq$ n $\leq$ $3 \times 10^4$
group.length $==$ beforeItems.length $==$ n
$-1 \leq$ group[i] $\leq$ m - $1$
$0 \leq$ beforeItems[i].length $\leq$ n - $1$
$0 \leq$ beforeItems[i][j] $\leq$ n - $1$
i $!=$ beforeItems[i][j]
beforeItems[i] does not contain duplicate elements.

Problem: Sort Items by Groups Respecting Dependencies

Statement

Examples

Understand the problem

Figure it out!

Try it yourself

Problem: Sort Items by Groups Respecting Dependencies

Statement

Examples

Understand the problem

Figure it out!

Try it yourself