Leetcode 1203. Sort Items by Groups Respecting Dependencies
The problem is about grouping lists of integers such that each group maintains the order provided in another list.
For example, in the list group = [-1,-1,1,0,0,1,0,-1]
, numbers at index 2,5 are in group 1 and numbers at index 3,4,6 are in group 0. Also, number at each index should come only after numbers mentioned in beforeItems
at that index. Like number at index 4 can come only after number at index 3 and 6 in the sorted list.
Solution Approach
The problem approach can be solved using Topological Sorting and Depth-First Search. This involves creating a graph of dependencies and performing Topologically sorting it to form multiple groups such that each element in a group has lower priority than its next element and all elements in a group have higher priority than elements in the next group.
Topological Sorting is used to find a linear ordering of the vertices in a Directed Acyclic Graph (DAG) such that for every directed edge u -> v, vertex u comes before vertex v in the ordering.
DFS is used to generate the Topological Sorting order.
Example
Let's assume n=5, m=5, group=[-1,0,3,1,-1] and beforeItems=[[],[2,3,4],[],[],[]]. The problem asks to generate several groups out of these items i.e., 0,1,2,3,4 such that elements in group[i] come after elements in group[i-1] and also follow the rule specified by beforeItems.
Firstly, construct a graph of dependencies :
- item 0 is grouped under 0+n = 0+5 = 5
- item 1 has dependencies on 2,3,4. 1 is grouped under 0+n = 0+5 = 5
- item 3 is grouped under 1+n = 1+5 = 6
- No dependencies for items 2 and 4
Then perform a DFS and find the topological order which results [4,2,1,0,3]
Solution
Python Solution
1 2python 3from collections import defaultdict,deque 4class Solution: 5 def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]: 6 def topological_sort(vertices,edges): 7 indegrees = [0]*(vertices) 8 for u in range(vertices): 9 for v in edges[u]: 10 indegrees[v] += 1 11 12 queue = deque([u for u in range(vertices) if indegrees[u] == 0]) 13 order=[] 14 while queue: 15 u = queue.popleft() 16 order.append(u) 17 for v in edges[u]: 18 indegrees[v] -= 1 19 if indegrees[v] == 0: 20 queue.append(v) 21 return order if len(order) == vertices else [] 22 23 for i in range(n): 24 if group[i] == -1: 25 group[i] = m 26 m += 1 27 28 group_edges=defaultdict(list) 29 group_indegrees=[0]*m 30 item_edges=defaultdict(list) 31 item_indegrees=[0]*n 32 33 for i in range(n): 34 for b in beforeItems[i]: 35 if group[i] == group[b]: 36 item_edges[b].append(i) 37 item_indegrees[i] += 1 38 else: 39 group_edges[group[b]].append(group[i]) 40 group_indegrees[group[i]] += 1 41 42 item_order = topological_sort(n,item_edges) 43 group_order = topological_sort(m,group_edges) 44 45 if not item_order or not group_order: 46 return [] 47 48 group_index, items_in_group=defaultdict(list),defaultdict(list) 49 50 for i, g in enumerate(group_order): 51 group_index[g] = i 52 53 for i in item_order: 54 items_in_group[group[i]].append(i) 55 56 res=[] 57 58 for g in range(m): 59 for i in items_in_group[group_order[g]]: 60 res.append(i) 61 62 return res
Java Solution
1 2java 3 4class Solution { 5 public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) { 6 // create a new group for each item assigned a group of -1 7 int num_of_groups = 0; 8 for (int i = 0; i < group.length; i++) { 9 if (group[i] == -1) { 10 group[i] = n + m + num_of_groups++; 11 } 12 } 13 14 // initialize graph of groups and graph of items in each group 15 ArrayList<Integer>[] graph_groups = new ArrayList[n + m + num_of_groups]; 16 ArrayList<Integer>[] graph_items = new ArrayList[n]; 17 18 // initialization graphs 19 for (int i = 0; i < n + m + num_of_groups; i++) { 20 graph_groups[i] = new ArrayList<Integer>(); 21 } 22 23 for (int i = 0; i < n; i++) { 24 graph_items[i] = new ArrayList<Integer>(); 25 } 26 27 // create edges between each item's group and the groups of items that should come before this item 28 int[] indegrees_groups = new int[n + m + num_of_groups]; // number of items that should come before 29 30 for (int i = 0; i < n; i++) { 31 // add group to item's group 32 graph_groups[group[i]].add(i); 33 // add edges between groups and items within each group 34 for (int j : beforeItems.get(i)) { 35 if (group[j] != group[i]) { 36 graph_groups[group[j]].add(group[i]); 37 indegrees_groups[group[i]]++; 38 }else { 39 graph_items[j].add(i); 40 } 41 } 42 } 43 44 // topologically sort groups 45 int[] sorted_groups = topologicallySort(graph_groups, indegrees_groups); 46 if (sorted_groups.length != n + m + num_of_groups)return new int[]{}; // if a cycle is found 47 48 // for all items in each group, sort them where the groups' order is preserved 49 int[] sorted_items = new int[n]; 50 int k = 0; 51 for (int i = 0; i < sorted_groups.length; i++) { 52 int[] sorted_items_in_group = topologicallySort(graph_items, sorted_groups[i], n); 53 if (sorted_items_in_group.length != graph_groups[sorted_groups[i]].size()) return new int[]{}; // if a cycle is found 54 // add the current group's items to the output list 55 for (int j = 0; j < sorted_items_in_group.length; j++) { 56 sorted_items[k++] = sorted_items_in_group[j]; 57 } 58 } 59 return sorted_items; 60 } 61 62 //The Kahnโs algorithm to find a valid topological order is used 63 private int[] topologicallySort(ArrayList<Integer>[] graph, int[] indegrees) { 64 int[] output = new int[indegrees.length]; 65 int k = 0; 66 LinkedList<Integer> queue = new LinkedList<Integer>(); 67 for (int i = 0; i < indegrees.length; i++) { 68 if (indegrees[i] == 0)queue.addLast(i); 69 } 70 while (!queue.isEmpty()) { 71 int node = queue.removeFirst(); 72 output[k++] = node; 73 for (int neigh : graph[node]) { 74 if (--indegrees[neigh] == 0)queue.addLast(neigh); 75 } 76 } 77 return k == output.length ? output : new int[]{}; 78 } 79 80 private int[] topologicallySort(ArrayList<Integer>[] graph, int group, int n) { 81 int[] output = new int[n]; 82 int k = 0; 83 int[] temp_indegrees = new int[n]; 84 85 LinkedList<Integer> queue = new LinkedList<Integer>(); 86 for (int node : graph[group]) { 87 for (int neigh : graph[node]) { 88 temp_indegrees[neigh]++; 89 } 90 } 91 for (int node : graph[group]) { 92 if (temp_indegrees[node] == 0)queue.addLast(node); 93 } 94 while (!queue.isEmpty()) { 95 int node = queue.removeFirst(); 96 output[k++] = node; 97 for (int neigh : graph[node]) { 98 if (--temp_indegrees[neigh] == 0)queue.addLast(neigh); 99 } 100 } 101 102 return k == output.length ? output : new int[]{}; 103 } 104}
C++ Solution
1
2c++
3class Solution {
4public:
5 vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
6 vector<vector<int>> graph(n + m);
7 vector<int> inDegree(n + m);
8
9 for (int i = 0; i < group.size(); ++i) {
10 if (group[i] == -1)
11 continue;
12 graph[group[i] + n].push_back(i);
13 ++inDegree[i];
14 }
15
16 for (int i = 0; i < beforeItems.size(); ++i)
17 for (const int& b : beforeItems[i]) {
18 const int u = group[b] == -1 ? b : group[b] + n;
19 const int v = group[i] == -1 ? i : group[i] + n;
20 if (u == v) {
21 graph[b].push_back(i);
22 ++inDegree[i];
23 } else {
24 graph[u].push_back(v);
25 ++inDegree[v];
26 }
27 }
28
29 vector<int> ans;
30
31 for (int i = 0; i < n + m; ++i)
32 if (inDegree[i] == 0)
33 dfs(graph, i, inDegree, n, ans);
34
35 return ans.size() == n ? ans : vector<int>();
36 }
37
38private:
39 void dfs(const vector<vector<int>>& graph, int u, vector<int>& inDegree,
40 int n, vector<int>& ans) {
41 if (u < n)
42 ans.push_back(u);
43
44 inDegree[u] = -1;
45
46 for (const int& v : graph[u])
47 if (--inDegree[v] == 0)
48 dfs(graph, v, inDegree, n, ans);
49 }
50};
Javascript Solution
1
2javascript
3var sortItems = function(n, m, group, beforeItems) {
4 const nGroup = Math.max(...group) + 1;
5 const graph = Array(n + nGroup).fill(0).map(() => []);
6 const inDegrees = Array(n + nGroup).fill(0);
7
8 for(let [index, val] of group.entries()){
9 if(val === -1) {
10 group[index] = m;
11 m +=1;
12 }
13 }
14
15 for(let i=0; i<n; i++) {
16 for(let j=0; j<beforeItems[i].length; j++) {
17 let item = beforeItems[i][j];
18 if(group[item] === group[i]) {
19 graph[item].push(i);
20 inDegrees[i]++;
21 }else{
22 graph[group[item] + n].push(group[i] + n);
23 inDegrees[group[i] + n]++;
24 }
25 }
26 graph[i].push(group[i] + n);
27 inDegrees[group[i] + n]++;
28 }
29
30 let topoOrder = topologicalSort(graph, inDegrees, inDegrees.length);
31 if(topoOrder.length){
32 return topoOrder.filter((item) => item < n);
33 }else{
34 return [];
35 }
36};
37
38function topologicalSort(graph, inDegrees, n) {
39 let zeroInDegrees = [];
40 for(let i=0; i<n; i++) {
41 if(inDegrees[i] === 0) {
42 zeroInDegrees.push(i);
43 }
44 }
45 let topoOrder = [];
46
47 while(zeroInDegrees.length){
48 let node = zeroInDegrees.shift();
49 topoOrder.push(node);
50 for(let i=0; i<graph[node].length; i++) {
51 inDegrees[graph[node][i]]--;
52 if(inDegrees[graph[node][i]] === 0){
53 zeroInDegrees.push(graph[node][i]);
54 }
55 }
56 }
57 if(topoOrder.length !== n) return [];
58 return topoOrder;
59}
In the provided Python, Java, C++ and Javascript solutions, the problem is first solved by creating a graph and adding dependencies into it. Again if a group is not formed (-1), then another group is added. Creating edges between the items of each group is done next. Finally a helper function is created to handle the Topological Ordering. The code can handle any list length and is a perfect implementation of graph theory in real world problems.
Out of the four solutions provided, Python and JavaScript solutions are relatively simpler to understand, as they use built-in functions to reduce code complexity. Java and C++ follow similar approach but with more code to handle List and Array data structures. It is important to notice the translation of algorithm into these languages. Despite their different syntax and structure, they can solve complex problems with same efficiency, demonstrating the flexibility and power of programming languages.
In sum, these solutions provide an excellent demonstration of how to use topological sorting and DFS to group elements according to their dependencies. The implementations in Python, Java, C++ and JavaScript allow developers in any of these languages to solve the problem effectively and efficiently. This serves as a great starting point to further explore topological sorting, DFS or algorithms related to graph theory.
Got a question?ย Ask the Teaching Assistantย anything you don't understand.
Still not clear? Ask in the Forum, ย Discordย orย Submitย the part you don't understand to our editors.