LeetCode [1203] Sort Items by Groups Respecting Dependencies

 1203. Sort Items by Groups Respecting Dependencies

Hard

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*10^4
• 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.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62

/* for group i, its previous node is n+2*i, its next node is n+2*i+1 */ class Solution { Map<Integer, Set<Integer>> links = new HashMap<>(); public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) { for(int i=0; i<n; ++i){ if(group[i]!=-1){//n+2*group[i]->i->n+2*group[i]+1 links.computeIfAbsent(n+2*group[i], k->new HashSet<>()).add(i); links.computeIfAbsent(i, k->new HashSet<>()).add(n+2*group[i]+1); } } for(int i = 0; i<n; ++i){ for(int j : beforeItems.get(i)){//j->i if(group[i]==group[j]){ links.computeIfAbsent(j, k->new HashSet<>()).add(i); }else{ if(group[j]==-1){//j->n+2*group[i] links.computeIfAbsent(j, k->new HashSet<>()).add(n+2*group[i]); }else if(group[i]==-1){//n+2*group[j]+1->i links.computeIfAbsent(n+2*group[j]+1, k->new HashSet<>()).add(i); }else{//n+2*group[j]+1->n+2*group[i] links.computeIfAbsent(n+2*group[j]+1, k->new HashSet<>()).add(n+2*group[i]); } } } } Set<Integer> visited = new HashSet<>(); Set<Integer> path = new HashSet<>(); List<Integer> sorted = new ArrayList<>(); for(int item = n+2*m-1; item>=0; --item){//must call from group bound nodes to push the same group items together if(visited.contains(item)) continue; path.add(item); if(hasCycle(item, visited, path, sorted)) return new int[0]; path.remove(item); } int[] ret = new int[n]; int i = 0; for(int item : sorted){ if(item<n) ret[i++] = item; } return ret; } boolean hasCycle(int item, Set<Integer> visited, Set<Integer> path, List<Integer> sorted){ visited.add(item); if(links.containsKey(item)){ for(int next : links.get(item)){ if(path.contains(next)) return true; if(visited.contains(next)) continue; path.add(next); if(hasCycle(next, visited, path, sorted)) return true; path.remove(next); } } sorted.add(0, item); return false; } }