Sort Items by Groups Respecting Dependencies

Given n items, group assignments, and dependency relations, return a valid ordering of the items that respects both item dependencies and group boundaries. Return an empty array if no valid ordering exists. Pattern focus: Applications. This is one of the best real-world topological sorting applications.

Input Format

n = number of items, m = number of groups, group = group id per item, beforeItems = prerequisites for each item

Output Format

a valid item order or an empty array

Constraints

  • 1 <= input size <= 10^5
  • -10^9 <= numeric values <= 10^9

Examples

Example 1:

Input:

n = 8
m = 2
group = [-1,-1,1,0,0,1,0,-1]
beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]

Output:

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

Explanation:

This is a standard valid ordering that respects both item and group dependencies.

Example 2:

Input:

n = 3
m = 1
group = [0,0,0]
beforeItems = [[1],[2],[0]]

Output:

[]

Explanation:

The items form a cycle, so no valid ordering exists.

Example 3:

Input:

n = 4
m = 2
group = [0,0,1,1]
beforeItems = [[],[0],[1],[2]]

Output:

[0,1,2,3]

Explanation:

The dependencies force a single valid order.

Loading...
Sort Items by Groups Respecting Dependencies