1203. Sort Items by Groups Respecting Dependencies - Leetcode Solution

Problem Description

You are given n items, each belonging to zero or one group. The group assignment for each item is given by the array group, where group[i] is the group id for item i, or -1 if item i does not belong to any group. There are m groups in total, numbered from 0 to m-1.

You are also given a list beforeItems, where beforeItems[i] is a list of items that must come before item i in the final ordering.

Your task is to return a list of the items sorted such that:

Every item appears exactly once.
Items belonging to the same group appear together in the result.
For every dependency j in beforeItems[i], j comes before i in the list.

If there is no valid ordering, return an empty list.

Key constraints:

Each item appears only once in the result.
Items from the same group must be contiguous in the output.
All dependencies must be respected.

Thought Process

At first glance, this problem is similar to topological sorting with dependencies. However, it adds another layer of complexity by introducing groups: all items from the same group must be together. This means we need to sort both items and groups while respecting dependencies at both levels.

A brute-force approach might try all permutations, but this is computationally infeasible given the constraints. Instead, we realize that if we can topologically sort the groups and, within each group, topologically sort the items, we can combine these results to create the required ordering.

The challenge is handling items that do not belong to any group and dependencies that cross group boundaries. We need a way to assign unique group ids to ungrouped items, so every item is associated with one group.

Solution Approach

To solve the problem efficiently, we'll use a two-level topological sort:

Assign unique group ids to ungrouped items:
- For each item with group[i] == -1, assign a new group id starting from m upwards.
Build dependency graphs:
- Item-level graph: For each dependency j in beforeItems[i], add an edge from j to i.
- Group-level graph: If group[i] != group[j] for a dependency j in beforeItems[i], add an edge from group[j] to group[i].
Topologically sort the groups:
- If sorting is not possible due to a cycle, return an empty list.
Topologically sort the items within each group:
- For each group, collect its items and sort them according to item-level dependencies.
- If sorting is not possible due to a cycle, return an empty list.
Assemble the final result:
- For each group in the sorted group order, append its sorted items to the result.

We use adjacency lists and in-degree counts for both item and group graphs to perform Kahn's algorithm for topological sorting. Hash maps are used for quick lookups and grouping.

Example Walkthrough

Let's consider an example:
Input:

n = 8, m = 2
group = [-1,0,0,1,-1,-1,1,0]
beforeItems = [[],[6],[5],[6],[3,6],[],[],[]]

Step-by-step:

Assign group ids:
- Items 0, 4, and 5 have group = -1. Assign group ids 2, 3, and 4 respectively.
Build graphs:
- Item dependencies: 1 depends on 6, 2 on 5, 3 on 6, 4 on 3 and 6.
- Group dependencies: group of 1 (0) depends on group of 6 (1), etc.
Topological sort groups:
- Find an order such as [2, 0, 4, 3, 1] (actual order may vary if multiple are valid).
Topological sort items within groups:
- For each group, sort its items based on item dependencies.
Assemble result:
- Result might be [0,1,2,5,4,3,6,7] (as long as all constraints are met).

At each step, we ensure that all dependencies and group contiguity are respected.

Time and Space Complexity

Brute-force approach:

Trying all permutations is O(n!) and infeasible for large n.

Optimized approach:

Time Complexity:
- Building graphs: O(n + e), where e is the total number of dependencies.
- Topological sorts: O(n + e) for both item and group graphs.
- Total: O(n + e).
Space Complexity:
- Adjacency lists and in-degree arrays: O(n + e).
- Grouping structures: O(n).

This is efficient and suitable for large inputs.

Summary

By recognizing the need for two-layered topological sorting—first on groups, then on items within groups—we can efficiently solve the problem while respecting all constraints. Assigning unique group ids to ungrouped items simplifies the logic. The use of Kahn's algorithm ensures we detect cycles and return an empty list if no solution exists. The elegance of this approach lies in decomposing the problem into manageable subproblems and using classic graph algorithms to solve them.

Code Implementation

from collections import defaultdict, deque
from typing import List

class Solution:
    def sortItems(self, n: int, m: int, group: List[int], beforeItems: List[List[int]]) -> List[int]:
        # Assign unique group ids to ungrouped items
        new_group_id = m
        for i in range(n):
            if group[i] == -1:
                group[i] = new_group_id
                new_group_id += 1

        group_items = defaultdict(list)
        for i in range(n):
            group_items[group[i]].append(i)

        # Build item and group dependency graphs
        item_graph = defaultdict(list)
        item_indegree = [0] * n
        group_graph = defaultdict(list)
        group_indegree = defaultdict(int)

        for i in range(n):
            for pre in beforeItems[i]:
                item_graph[pre].append(i)
                item_indegree[i] += 1
                if group[i] != group[pre]:
                    group_graph[group[pre]].append(group[i])
                    group_indegree[group[i]] += 1

        def topological_sort(nodes, graph, indegree):
            res = []
            queue = deque([node for node in nodes if indegree[node] == 0])
            while queue:
                u = queue.popleft()
                res.append(u)
                for v in graph[u]:
                    indegree[v] -= 1
                    if indegree[v] == 0:
                        queue.append(v)
            if len(res) == len(nodes):
                return res
            else:
                return []

        # Sort groups
        all_groups = list(group_items.keys())
        group_order = topological_sort(all_groups, group_graph, group_indegree.copy())
        if not group_order:
            return []

        result = []
        for grp in group_order:
            items = group_items[grp]
            if not items:
                continue
            # Sort items in this group
            sub_graph = defaultdict(list)
            sub_indegree = {}
            for i in items:
                sub_indegree[i] = item_indegree[i]
            for i in items:
                for v in item_graph[i]:
                    if v in sub_indegree:
                        sub_graph[i].append(v)
            item_order = topological_sort(items, sub_graph, sub_indegree)
            if not item_order:
                return []
            result.extend(item_order)
        return result

#include <vector>
#include <queue>
#include <unordered_map>
#include <unordered_set>
using namespace std;

class Solution {
public:
    vector<int> sortItems(int n, int m, vector<int>& group, vector<vector<int>>& beforeItems) {
        int newGroupId = m;
        for (int i = 0; i < n; ++i) {
            if (group[i] == -1) {
                group[i] = newGroupId++;
            }
        }
        unordered_map<int, vector<int>> groupItems;
        for (int i = 0; i < n; ++i) {
            groupItems[group[i]].push_back(i);
        }

        vector<vector<int>> itemGraph(n);
        vector<int> itemIndegree(n, 0);
        unordered_map<int, vector<int>> groupGraph;
        unordered_map<int, int> groupIndegree;

        for (int i = 0; i < n; ++i) {
            for (int pre : beforeItems[i]) {
                itemGraph[pre].push_back(i);
                itemIndegree[i]++;
                if (group[i] != group[pre]) {
                    groupGraph[group[pre]].push_back(group[i]);
                    groupIndegree[group[i]]++;
                }
            }
        }

        auto topoSort = [](const vector<int>& nodes, unordered_map<int, vector<int>>& graph, unordered_map<int, int> indegree) {
            vector<int> res;
            queue<int> q;
            for (int node : nodes) {
                if (indegree[node] == 0) q.push(node);
            }
            while (!q.empty()) {
                int u = q.front(); q.pop();
                res.push_back(u);
                for (int v : graph[u]) {
                    indegree[v]--;
                    if (indegree[v] == 0) q.push(v);
                }
            }
            if (res.size() == nodes.size()) return res;
            return vector<int>();
        };

        vector<int> allGroups;
        for (auto& kv : groupItems) allGroups.push_back(kv.first);
        vector<int> groupOrder = topoSort(allGroups, groupGraph, groupIndegree);
        if (groupOrder.empty()) return {};

        vector<int> result;
        for (int grp : groupOrder) {
            vector<int>& items = groupItems[grp];
            if (items.empty()) continue;
            unordered_map<int, vector<int>> subGraph;
            unordered_map<int, int> subIndegree;
            for (int i : items) subIndegree[i] = itemIndegree[i];
            for (int i : items) {
                for (int v : itemGraph[i]) {
                    if (subIndegree.count(v)) subGraph[i].push_back(v);
                }
            }
            vector<int> itemOrder = topoSort(items, subGraph, subIndegree);
            if (itemOrder.empty()) return {};
            result.insert(result.end(), itemOrder.begin(), itemOrder.end());
        }
        return result;
    }
};

import java.util.*;

class Solution {
    public List<Integer> sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
        int newGroupId = m;
        for (int i = 0; i < n; i++) {
            if (group[i] == -1) {
                group[i] = newGroupId++;
            }
        }
        Map<Integer, List<Integer>> groupItems = new HashMap<>();
        for (int i = 0; i < n; i++) {
            groupItems.computeIfAbsent(group[i], k -> new ArrayList<>()).add(i);
        }

        List<List<Integer>> itemGraph = new ArrayList<>();
        for (int i = 0; i < n; i++) itemGraph.add(new ArrayList<>());
        int[] itemIndegree = new int[n];
        Map<Integer, List<Integer>> groupGraph = new HashMap<>();
        Map<Integer, Integer> groupIndegree = new HashMap<>();

        for (int i = 0; i < n; i++) {
            for (int pre : beforeItems.get(i)) {
                itemGraph.get(pre).add(i);
                itemIndegree[i]++;
                if (group[i] != group[pre]) {
                    groupGraph.computeIfAbsent(group[pre], k -> new ArrayList<>()).add(group[i]);
                    groupIndegree.put(group[i], groupIndegree.getOrDefault(group[i], 0) + 1);
                }
            }
        }

        List<Integer> allGroups = new ArrayList<>(groupItems.keySet());
        List<Integer> groupOrder = topoSort(allGroups, groupGraph, groupIndegree);
        if (groupOrder.isEmpty()) return new ArrayList<>();

        List<Integer> result = new ArrayList<>();
        for (int grp : groupOrder) {
            List<Integer> items = groupItems.get(grp);
            if (items == null || items.isEmpty()) continue;
            Map<Integer, List<Integer>> subGraph = new HashMap<>();
            Map<Integer, Integer> subIndegree = new HashMap<>();
            for (int i : items) subIndegree.put(i, itemIndegree[i]);
            for (int i : items) {
                for (int v : itemGraph.get(i)) {
                    if (subIndegree.containsKey(v)) {
                        subGraph.computeIfAbsent(i, k -> new ArrayList<>()).add(v);
                    }
                }
            }
            List<Integer> itemOrder = topoSort(items, subGraph, subIndegree);
            if (itemOrder.isEmpty()) return new ArrayList<>();
            result.addAll(itemOrder);
        }
        return result;
    }

    private List<Integer> topoSort(List<Integer> nodes, Map<Integer, List<Integer>> graph, Map<Integer, Integer> indegree) {
        List<Integer> res = new ArrayList<>();
        Queue<Integer> q = new LinkedList<>();
        for (int node : nodes) {
            if (indegree.getOrDefault(node, 0) == 0) q.offer(node);
        }
        while (!q.isEmpty()) {
            int u = q.poll();
            res.add(u);
            for (int v : graph.getOrDefault(u, Collections.emptyList())) {
                indegree.put(v, indegree.get(v) - 1);
                if (indegree.get(v) == 0) q.offer(v);
            }
        }
        if (res.size() == nodes.size()) return res;
        return new ArrayList<>();
    }
}

/**
 * @param {number} n
 * @param {number} m
 * @param {number[]} group
 * @param {number[][]} beforeItems
 * @return {number[]}
 */
var sortItems = function(n, m, group, beforeItems) {
    let newGroupId = m;
    for (let i = 0; i < n; ++i) {
        if (group[i] === -1) {
            group[i] = newGroupId++;
        }
    }
    let groupItems = new Map();
    for (let i = 0; i < n; ++i) {
        if (!groupItems.has(group[i])) groupItems.set(group[i], []);
        groupItems.get(group[i]).push(i);
    }

    let itemGraph = Array.from({length: n}, () => []);
    let itemIndegree = Array(n).fill(0);
    let groupGraph = new Map();
    let groupIndegree = new Map();

    for (let i = 0; i < n; ++i) {
        for (let pre of beforeItems[i]) {
            itemGraph[pre].push(i);
            itemIndegree[i]++;
            if (group[i] !== group[pre]) {
                if (!groupGraph.has(group[pre])) groupGraph.set(group[pre], []);
                groupGraph.get(group[pre]).push(group[i]);
                groupIndegree.set(group[i], (groupIndegree.get(group[i]) || 0) + 1);
            }
        }
    }

    function topoSort(nodes, graph, indegree) {
        let res = [];
        let queue = [];
        for (let node of nodes) {
            if ((indegree.get ? indegree.get(node) : indegree[node]) === 0) queue.push(node);
        }
        while (queue.length) {
            let u = queue.shift();
            res.push(u);
            for (let v of (graph.get ? graph.get(u) || [] : graph[u] || [])) {
                if (indegree.set) {
                    indegree.set(v, indegree.get(v) - 1);
                    if (indegree.get(v) === 0) queue.push(v);
                } else {
                    indegree[v]--;
                    if (indegree[v] === 0) queue.push(v);
                }
            }
        }
        if (res.length === nodes.length) return res;
        return [];
    }

    let allGroups = Array.from(groupItems.keys());
    let groupOrder = topoSort(allGroups, groupGraph, groupIndegree);
    if (!groupOrder.length) return [];

    let result = [];
    for (let grp of groupOrder) {
        let items = groupItems.get(grp);
        if (!items || !items.length) continue;
        let subGraph = new Map();
        let subIndegree = new Map();
        for (let i of items) subIndegree.set(i, itemIndegree[i]);
        for (let i of items) {
            for (let v of itemGraph[i]) {
                if (subIndegree.has(v)) {
                    if (!subGraph.has(i)) subGraph.set(i, []);
                    subGraph.get(i).push(v);
                }
            }
        }
        let itemOrder = topoSort(items, subGraph, subIndegree);
        if (!itemOrder.length) return [];
        result.push(...itemOrder);
    }
    return result;
};

AlgoMap.io

Want Help Cracking FAANG?