1203. Sort Items by Groups Respecting Dependencies

Description

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 i-th item in the sorted array (to the left of the i-th 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.

 

Solutions

Solution: Topological Sort

• Time complexity: O(n+m+n*k)
• Space complexity: O(n+m+n*k)

 

JavaScript

/**
 * @param {number} n
 * @param {number} m
 * @param {number[]} group
 * @param {number[][]} beforeItems
 * @return {number[]}
 */
const sortItems = function (n, m, group, beforeItems) {
  const graph = Array.from({ length: n + m }, () => []);
  const indegree = Array.from({ length: n + m }, () => 0);

  for (let index = 0; index < n; index++) {
    if (group[index] === -1) continue;

    graph[n + group[index]].push(index);
    indegree[index] += 1;
  }

  for (let index = 0; index < n; index++) {
    const item = group[index] === -1 ? index : n + group[index];

    for (const before of beforeItems[index]) {
      const beforeItem = group[before] === -1 ? before : n + group[before];

      if (item === beforeItem) {
        graph[before].push(index);
        indegree[index] += 1;
      } else {
        graph[beforeItem].push(item);
        indegree[item] += 1;
      }
    }
  }
  const result = [];

  const dfs = item => {
    if (item < n) result.push(item);

    indegree[item] = -1;

    for (const next of graph[item] ?? []) {
      indegree[next] -= 1;

      if (!indegree[next]) dfs(next);
    }
  };

  for (let index = 0; index < n + m; index++) {
    if (!indegree[index]) dfs(index);
  }
  return result.length < n ? [] : result;
};