1203. Sort Items by Groups Respecting Dependencies LeetCode Solution

In this guide, you will get 1203. Sort Items by Groups Respecting Dependencies LeetCode Solution with the best time and space complexity. The solution to Sort Items by Groups Respecting Dependencies problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Sort Items by Groups Respecting Dependencies solution in C++
4. Sort Items by Groups Respecting Dependencies solution in Java
5. Sort Items by Groups Respecting Dependencies solution in Python
6. Additional Resources

Problem Statement of Sort Items by Groups Respecting Dependencies

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 * 104
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.

Complexity Analysis

• Time Complexity: O(|V| + |E|), where |V| = n + m and |E| = |\texttt{group[i]}| \ne -1 + |\texttt{items[i]}| \in \texttt{beforeItems}
• Space Complexity: O(|V| + |E|)

1203. Sort Items by Groups Respecting Dependencies LeetCode Solution in C++

class Solution {
 public:
  vector<int> sortItems(int n, int m, vector<int>& group,
                        vector<vector<int>>& beforeItems) {
    vector<vector<int>> graph(n + m);
    vector<int> inDegrees(n + m);

    // Build the graph by remapping the k-th group to k + n imaginary node.
    for (int i = 0; i < group.size(); ++i) {
      if (group[i] == -1)
        continue;
      graph[group[i] + n].push_back(i);
      ++inDegrees[i];
    }

    for (int i = 0; i < beforeItems.size(); ++i)
      for (const int b : beforeItems[i]) {
        const int u = group[b] == -1 ? b : group[b] + n;
        const int v = group[i] == -1 ? i : group[i] + n;
        if (u == v) {  // u and v are already in the same group.
          graph[b].push_back(i);
          ++inDegrees[i];
        } else {
          graph[u].push_back(v);
          ++inDegrees[v];
        }
      }

    // Perform topological sorting.
    vector<int> ans;

    for (int i = 0; i < n + m; ++i)
      if (inDegrees[i] == 0)  // inDegrees[i] == -1 means visited.
        dfs(graph, i, inDegrees, n, ans);

    return ans.size() == n ? ans : vector<int>();
  }

 private:
  void dfs(const vector<vector<int>>& graph, int u, vector<int>& inDegrees,
           int n, vector<int>& ans) {
    if (u < n)
      ans.push_back(u);

    inDegrees[u] = -1;  // Mark as visited.

    for (const int v : graph[u])
      if (--inDegrees[v] == 0)
        dfs(graph, v, inDegrees, n, ans);
  }
};
/* code provided by PROGIEZ */

1203. Sort Items by Groups Respecting Dependencies LeetCode Solution in Java

class Solution {
  public int[] sortItems(int n, int m, int[] group, List<List<Integer>> beforeItems) {
    List<Integer>[] graph = new List[n + m];
    int[] inDegrees = new int[n + m];

    for (int i = 0; i < graph.length; ++i)
      graph[i] = new ArrayList<>();

    // Build the graph by remapping the k-th group to k + n imaginary node.
    for (int i = 0; i < group.length; ++i) {
      if (group[i] == -1)
        continue;
      graph[group[i] + n].add(i);
      ++inDegrees[i];
    }

    for (int i = 0; i < beforeItems.size(); ++i)
      for (final int b : beforeItems.get(i)) {
        final int u = group[b] == -1 ? b : group[b] + n;
        final int v = group[i] == -1 ? i : group[i] + n;
        if (u == v) { // u and v are already in the same group.
          graph[b].add(i);
          ++inDegrees[i];
        } else {
          graph[u].add(v);
          ++inDegrees[v];
        }
      }

    // Perform topological sorting.
    List<Integer> ans = new ArrayList<>();

    for (int i = 0; i < n + m; ++i)
      if (inDegrees[i] == 0) // inDegrees[i] == -1 means visited.
        dfs(graph, i, inDegrees, n, ans);

    return ans.size() == n ? ans.stream().mapToInt(Integer::intValue).toArray() : new int[] {};
  }

  private void dfs(List<Integer>[] graph, int u, int[] inDegrees, int n, List<Integer> ans) {
    if (u < n)
      ans.add(u);

    inDegrees[u] = -1; // Mark as visited.

    for (final int v : graph[u])
      if (--inDegrees[v] == 0)
        dfs(graph, v, inDegrees, n, ans);
  }
}
// code provided by PROGIEZ

1203. Sort Items by Groups Respecting Dependencies LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.