1203. Sort Items by Groups Respecting Dependencies

1203. Sort Items by Groups Respecting Dependencies #

Problem #

There are n items each belonging to zero or one of m groups where group[i] is the group that the i-th item belongs to and it’s equal to -1 if the i-th item belongs to no group. The items and the groups are zero indexed. A group can have no item belonging to it.

Return a sorted list of the items such that:

  • The items that belong to the same group are next to each other in the sorted list.
  • There are some relations between these items where beforeItems[i] is a list containing all the items that should come before the ith item in the sorted array (to the left of the ith item).

Return any solution if there is more than one solution and return an empty list if there is no solution.

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]

Example 2:

Input: n = 8, m = 2, group = [-1,-1,1,0,0,1,0,-1], beforeItems = [[],[6],[5],[6],[3],[],[4],[]]
Output: []
Explanation: This is the same as example 1 except that 4 needs to be before 6 in the sorted list.

Constraints:

  • 1 <= m <= n <= 3 * 104
  • group.length == beforeItems.length == n
  • 1 <= group[i] <= m - 1
  • 0 <= beforeItems[i].length <= n - 1
  • 0 <= beforeItems[i][j] <= n - 1
  • i != beforeItems[i][j]
  • beforeItems[i] does not contain duplicates elements.

Problem Summary #

There are n items, and each item either does not belong to any group or belongs to one of m groups. group[i] indicates the group that the i-th item belongs to; if the i-th item does not belong to any group, then group[i] equals -1. Both items and groups are zero-indexed. A group may be responsible for no items, meaning no item belongs to that group.

Please help arrange these items as required and return the sorted list of items:

  • Items in the same group should be adjacent to each other in the sorted list.
  • There are certain dependency relationships between items. We use a list beforeItems to represent them, where beforeItems[i] represents all items that should be completed before item i (located to the left of item i).

If multiple solutions exist, return any one of them. If there is no suitable solution, return an empty list.

Solution Ideas #

  • After reading the problem, we can determine that this is a topological sorting problem. However, what differs from a simple topological sort is that items within the same group need to be adjacent to each other. This can be solved with 2 topological sorts. The first topological sort determines the order between groups, and the second topological sort determines the order within each group. For implementation convenience, use a map to assign labels to virtual groups. As shown in the figure below, tasks 3, 4, and 6 are packaged into group 0; tasks 2 and 5 are packaged into group 1; and the other tasks each form their own group. The inter-group dependency is that task 6 depends on task 1. Since task 6 is encapsulated in group 0, group 3 depends on group 0. First sort between groups to determine the group order, then perform topological sorting within each group to produce the final order.

  • The above solution can AC, but it is too slow because it performs some unnecessary operations. Is it possible to use only one topological sort? Make the nodes that must stay together all depend on a single virtual node. For example, in the figure below, the virtual nodes are 8 and 9. 3, 4, and 6 all depend on task 8, while 2 and 5 both depend on task 9. Task 1 originally depends on task 6. Since 6 depends on 8, add an edge indicating that 1 depends on 8. By adding virtual nodes, the in-degrees of the nodes that need to be packaged together are increased. After constructing the above relationships, perform DFS in sequence according to the principle of in-degree being 0. The in-degrees of virtual nodes 8 and 9 are both 0, so performing DFS on them will definitely arrange all nodes associated with them together. This satisfies the requirement: items in the same group are adjacent to each other in the sorted list. After one pass, an order that satisfies the problem requirements is produced. This solution beats 100%!

Code #

package leetcode

// Solution 1: DFS version of topological sort
func sortItems(n int, m int, group []int, beforeItems [][]int) []int {
	groups, inDegrees := make([][]int, n+m), make([]int, n+m)
	for i, g := range group {
		if g > -1 {
			g += n
			groups[g] = append(groups[g], i)
			inDegrees[i]++
		}
	}
	for i, ancestors := range beforeItems {
		gi := group[i]
		if gi == -1 {
			gi = i
		} else {
			gi += n
		}
		for _, ancestor := range ancestors {
			ga := group[ancestor]
			if ga == -1 {
				ga = ancestor
			} else {
				ga += n
			}
			if gi == ga {
				groups[ancestor] = append(groups[ancestor], i)
				inDegrees[i]++
			} else {
				groups[ga] = append(groups[ga], gi)
				inDegrees[gi]++
			}
		}
	}
	res := []int{}
	for i, d := range inDegrees {
		if d == 0 {
			sortItemsDFS(i, n, &res, &inDegrees, &groups)
		}
	}
	if len(res) != n {
		return nil
	}
	return res
}

func sortItemsDFS(i, n int, res, inDegrees *[]int, groups *[][]int) {
	if i < n {
		*res = append(*res, i)
	}
	(*inDegrees)[i] = -1
	for _, ch := range (*groups)[i] {
		if (*inDegrees)[ch]--; (*inDegrees)[ch] == 0 {
			sortItemsDFS(ch, n, res, inDegrees, groups)
		}
	}
}

// Solution 2: two-dimensional topological sort, time complexity O(m+n), space complexity O(m+n)
func sortItems1(n int, m int, group []int, beforeItems [][]int) []int {
	groupItems, res := map[int][]int{}, []int{}
	for i := 0; i < len(group); i++ {
		if group[i] == -1 {
			group[i] = m + i
		}
		groupItems[group[i]] = append(groupItems[group[i]], i)
	}
	groupGraph, groupDegree, itemGraph, itemDegree := make([][]int, m+n), make([]int, m+n), make([][]int, n), make([]int, n)
	for i := 0; i < len(beforeItems); i++ {
		for j := 0; j < len(beforeItems[i]); j++ {
			if group[beforeItems[i][j]] != group[i] {
				// Items in different groups: determine inter-group dependencies
				groupGraph[group[beforeItems[i][j]]] = append(groupGraph[group[beforeItems[i][j]]], group[i])
				groupDegree[group[i]]++
			} else {
				// Items in the same group: determine intra-group dependencies
				itemGraph[beforeItems[i][j]] = append(itemGraph[beforeItems[i][j]], i)
				itemDegree[i]++
			}
		}
	}
	items := []int{}
	for i := 0; i < m+n; i++ {
		items = append(items, i)
	}
	// Inter-group topological sort
	groupOrders := topSort(groupGraph, groupDegree, items)
	if len(groupOrders) < len(items) {
		return nil
	}
	for i := 0; i < len(groupOrders); i++ {
		items := groupItems[groupOrders[i]]
		// Intra-group topological sort
		orders := topSort(itemGraph, itemDegree, items)
		if len(orders) < len(items) {
			return nil
		}
		res = append(res, orders...)
	}
	return res
}

func topSort(graph [][]int, deg, items []int) (orders []int) {
	q := []int{}
	for _, i := range items {
		if deg[i] == 0 {
			q = append(q, i)
		}
	}
	for len(q) > 0 {
		from := q[0]
		q = q[1:]
		orders = append(orders, from)
		for _, to := range graph[from] {
			deg[to]--
			if deg[to] == 0 {
				q = append(q, to)
			}
		}
	}
	return
}
  • Languages English
Calendar Jun 25, 2026
Edit Edit this page
Total visits:   You are visitor No.
中文