Formatted question description: https://leetcode.ca/all/1203.html

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.

Related Topics:
Depth-first Search, Graph, Topological Sort

Solution 1. Topological Sort

// OJ: https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/

// Time: O(M + N + E)
// Space: O(M + N + E)
class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        unordered_map<int, vector<int>> itemGraph; // adjacency list of items. Edges between groups are considered in groupGraph so ignored here.
        unordered_map<int, vector<int>> groupGraph; // adjacency list of groups.
        vector<int> itemIndegree(n); // in-degree of each item
        unordered_map<int, int> groupIndegree; // in-degree of each group
        unordered_map<int, vector<int>> itemInGroup; // map from group id to items in the group
        for (int i = 0; i < n; ++i) {
            if (group[i] == -1) group[i] = i + m; // make items without group to be in group `i + m` so that we can treat all the items the same
            itemInGroup[group[i]].push_back(i);
        }
        for (int i = 0; i < beforeItems.size(); ++i) {
            for (int j = 0; j < beforeItems[i].size(); ++j) {
                int from = beforeItems[i][j], to = i, fromGroup = group[from], toGroup = group[to];
                if (fromGroup == toGroup) { // If the edge is in the same group, update itemGraph and itemIndegree
                    itemGraph[from].push_back(to);
                    itemIndegree[to]++;
                } else { // If the edge is cross groups, update groupGraph and groupIndegree
                    groupGraph[fromGroup].push_back(toGroup);
                    groupIndegree[toGroup]++;
                }
            }
        }
        queue<int> groupQueue;
        for (auto &p : itemInGroup) { // Get the initial set of groups without indegree
            if (groupIndegree[p.first] == 0) groupQueue.push(p.first);
        }
        vector<int> ans;
        while (groupQueue.size()) {
            int gid = groupQueue.front();
            groupQueue.pop();
            queue<int> itemQueue; // do topological sort within the same group
            int itemCnt = 0;
            for (int u : itemInGroup[gid]) {
                if (itemIndegree[u] == 0) itemQueue.push(u);
            }
            while (itemQueue.size()) {
                int itemId = itemQueue.front();
                itemQueue.pop();
                ans.push_back(itemId);
                ++itemCnt;
                for (int v : itemGraph[itemId]) {
                    if (--itemIndegree[v] == 0) itemQueue.push(v);
                }
            }
            if (itemCnt != itemInGroup[gid].size()) return {}; // has circle within group, return empty list
            for (int v : groupGraph[gid]) {
                if (--groupIndegree[v] == 0) groupQueue.push(v);
            }
        }
        if (ans.size() != n) return {}; // has circle between group, return empty list
        return ans;
    }
};

Solution 2. Topological Sort

// OJ: https://leetcode.com/problems/sort-items-by-groups-respecting-dependencies/

// Time: O(M + N + E)
// Space: O(M + N + E)
class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        unordered_map<int, vector<int>> groupGraph, groupItems;
        unordered_map<int, int> groupIndegree;
        vector<int> groupOrder, ans;
        for (int i = 0; i < n; ++i) {
            int a = group[i] == -1 ? m + i : group[i];// For those items belonging to no group, let the groupId be `m + i`.
            if (a < m) groupItems[group[i]].push_back(i);
            if (groupGraph.count(a) == 0) groupGraph[a] = {};
            for (int j : beforeItems[i]) {
                int b = group[j] == -1 ? m + j : group[j];
                if (a == b) continue; // skip intra dependency
                groupGraph[b].push_back(a);
                groupIndegree[a]++;
            }
        }
        queue<int> q;
        for (auto &[g, _] : groupGraph) {
            if (groupIndegree[g] == 0) q.push(g); 
        }
        while (q.size()) {
            int u = q.front();
            q.pop();
            groupOrder.push_back(u);
            for (int v : groupGraph[u]) {
                if (--groupIndegree[v] == 0) q.push(v);
            }
        }
        if (groupOrder.size() != groupGraph.size()) return {};
        for (int g : groupOrder) {
            if (g >= m) {
                ans.push_back(g - m);
                continue;
            }
            unordered_map<int, vector<int>> itemGraph;
            unordered_map<int, int> itemIndegree;
            for (int u : groupItems[g]) {
                for (int v : beforeItems[u]) {
                    if (group[v] != g) continue;
                    itemGraph[v].push_back(u);
                    itemIndegree[u]++;
                }
            }
            for (int u : groupItems[g]) {
                if (itemIndegree[u] == 0) q.push(u);
            }
            int cnt = 0;
            while (q.size()) {
                int u = q.front();
                q.pop();
                ans.push_back(u);
                ++cnt;
                for (int v : itemGraph[u]) {
                    if (--itemIndegree[v] == 0) q.push(v);
                }
            }
            if (cnt != groupItems[g].size()) return {};
        }
        return ans;
    }
};

Java

class Solution {
    public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        for (int i = 0; i < n; i++) {
            if (group[i] == -1) {
                group[i] = m;
                m++;
            }
        }
        Map<Integer, Set<Integer>> groupOrderMap = new HashMap<Integer, Set<Integer>>();
        Map<Integer, Set<Integer>> itemOrderMap = new HashMap<Integer, Set<Integer>>();
        for (int i = 0; i < n; i++) {
            int currGroup = group[i];
            List<Integer> beforeList = beforeItems.get(i);
            for (int before : beforeList) {
                int prevGroup = group[before];
                Set<Integer> groupSet = groupOrderMap.getOrDefault(prevGroup, new HashSet<Integer>());
                groupSet.add(currGroup);
                groupOrderMap.put(prevGroup, groupSet);
                Set<Integer> itemSet = itemOrderMap.getOrDefault(before, new HashSet<Integer>());
                itemSet.add(i);
                itemOrderMap.put(before, itemSet);
            }
        }
        int[] groupIndegrees = new int[m];
        for (int i = 0; i < m; i++) {
            Set<Integer> set = groupOrderMap.getOrDefault(i, new HashSet<Integer>());
            for (int nextGroup : set) {
                if (nextGroup != i)
                    groupIndegrees[nextGroup]++;
            }
        }
        Queue<Integer> groupQueue = new LinkedList<Integer>();
        for (int i = 0; i < m; i++) {
            if (groupIndegrees[i] == 0)
                groupQueue.offer(i);
        }
        int[] groupsOrder = new int[m];
        int groupIndex = 0;
        while (!groupQueue.isEmpty()) {
            int currGroup = groupQueue.poll();
            groupsOrder[groupIndex] = currGroup;
            groupIndex++;
            Set<Integer> set = groupOrderMap.getOrDefault(currGroup, new HashSet<Integer>());
            for (int nextGroup : set) {
                groupIndegrees[nextGroup]--;
                if (groupIndegrees[nextGroup] == 0)
                    groupQueue.offer(nextGroup);
            }
        }
        if (groupIndex < m)
            return new int[0];
        Map<Integer, Set<Integer>> groupItemsMap = new HashMap<Integer, Set<Integer>>();
        for (int i = 0; i < n; i++) {
            int currGroup = group[i];
            Set<Integer> set = groupItemsMap.getOrDefault(currGroup, new HashSet<Integer>());
            set.add(i);
            groupItemsMap.put(currGroup, set);
        }
        int[] itemIndegrees = new int[n];
        for (int i = 0; i < n; i++) {
            Set<Integer> set = itemOrderMap.getOrDefault(i, new HashSet<Integer>());
            for (int nextItem : set)
                itemIndegrees[nextItem]++;
        }
        int[] itemsOrder = new int[n];
        int itemIndex = 0;
        for (int i = 0; i < m; i++) {
            int currGroup = groupsOrder[i];
            Set<Integer> itemSet = groupItemsMap.getOrDefault(currGroup, new HashSet<Integer>());
            Queue<Integer> itemQueue = new LinkedList<Integer>();
            for (int item : itemSet) {
                if (itemIndegrees[item] == 0)
                    itemQueue.offer(item);
            }
            while (!itemQueue.isEmpty()) {
                int item = itemQueue.poll();
                itemsOrder[itemIndex] = item;
                itemIndex++;
                Set<Integer> set = itemOrderMap.getOrDefault(item, new HashSet<Integer>());
                for (int nextItem : set) {
                    itemIndegrees[nextItem]--;
                    if (itemIndegrees[nextItem] == 0 && group[nextItem] == currGroup)
                        itemQueue.offer(nextItem);
                }
            }
        }
        if (itemIndex < n)
            return new int[0];
        else
            return itemsOrder;
    }
}

All Problems

All Solutions