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.