1203. 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\ast 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.

From: LeetCode
Link: 1203. Sort Items by Groups Respecting Dependencies

Solution:

Ideas:

give every -1 item its own group, topologically sort both item-dependencies and group-dependencies, then output items group by group.

Code:

#include <stdlib.h>
#include <string.h>

static int* topoSort(int nodes, int* head, int* to, int* next, int* indeg, int* returnCount) {
    int* q = (int*)malloc(sizeof(int) * nodes);
    int* order = (int*)malloc(sizeof(int) * nodes);
    int front = 0, back = 0, cnt = 0;

    for (int i = 0; i < nodes; i++) {
        if (indeg[i] == 0) q[back++] = i;
    }

    while (front < back) {
        int u = q[front++];
        order[cnt++] = u;

        for (int e = head[u]; e != -1; e = next[e]) {
            int v = to[e];
            indeg[v]--;
            if (indeg[v] == 0) q[back++] = v;
        }
    }

    free(q);

    if (cnt != nodes) {
        free(order);
        *returnCount = 0;
        return NULL;
    }

    *returnCount = cnt;
    return order;
}

/**
 * Note: The returned array must be malloced, assume caller calls free().
 */
int* sortItems(int n, int m, int* group, int groupSize,
               int** beforeItems, int beforeItemsSize,
               int* beforeItemsColSize, int* returnSize) {
    
    *returnSize = 0;

    int totalGroups = m;

    for (int i = 0; i < n; i++) {
        if (group[i] == -1) {
            group[i] = totalGroups++;
        }
    }

    int edgeCount = 0;
    for (int i = 0; i < n; i++) {
        edgeCount += beforeItemsColSize[i];
    }

    int* itemHead = (int*)malloc(sizeof(int) * n);
    int* groupHead = (int*)malloc(sizeof(int) * totalGroups);
    int* itemTo = (int*)malloc(sizeof(int) * edgeCount);
    int* itemNext = (int*)malloc(sizeof(int) * edgeCount);
    int* groupTo = (int*)malloc(sizeof(int) * edgeCount);
    int* groupNext = (int*)malloc(sizeof(int) * edgeCount);
    int* itemIndeg = (int*)calloc(n, sizeof(int));
    int* groupIndeg = (int*)calloc(totalGroups, sizeof(int));

    for (int i = 0; i < n; i++) itemHead[i] = -1;
    for (int i = 0; i < totalGroups; i++) groupHead[i] = -1;

    int itemEdges = 0, groupEdges = 0;

    for (int i = 0; i < n; i++) {
        for (int j = 0; j < beforeItemsColSize[i]; j++) {
            int pre = beforeItems[i][j];

            itemTo[itemEdges] = i;
            itemNext[itemEdges] = itemHead[pre];
            itemHead[pre] = itemEdges++;
            itemIndeg[i]++;

            if (group[pre] != group[i]) {
                groupTo[groupEdges] = group[i];
                groupNext[groupEdges] = groupHead[group[pre]];
                groupHead[group[pre]] = groupEdges++;
                groupIndeg[group[i]]++;
            }
        }
    }

    int itemCount = 0, groupCount = 0;
    int* itemOrder = topoSort(n, itemHead, itemTo, itemNext, itemIndeg, &itemCount);
    int* groupOrder = topoSort(totalGroups, groupHead, groupTo, groupNext, groupIndeg, &groupCount);

    if (!itemOrder || !groupOrder) {
        free(itemOrder);
        free(groupOrder);
        free(itemHead);
        free(groupHead);
        free(itemTo);
        free(itemNext);
        free(groupTo);
        free(groupNext);
        free(itemIndeg);
        free(groupIndeg);
        return (int*)malloc(0);
    }

    int* count = (int*)calloc(totalGroups + 1, sizeof(int));

    for (int i = 0; i < n; i++) {
        count[group[i] + 1]++;
    }

    for (int i = 1; i <= totalGroups; i++) {
        count[i] += count[i - 1];
    }

    int* pos = (int*)malloc(sizeof(int) * totalGroups);
    for (int i = 0; i < totalGroups; i++) {
        pos[i] = count[i];
    }

    int* bucket = (int*)malloc(sizeof(int) * n);

    for (int i = 0; i < n; i++) {
        int item = itemOrder[i];
        int g = group[item];
        bucket[pos[g]++] = item;
    }

    int* ans = (int*)malloc(sizeof(int) * n);
    int idx = 0;

    for (int i = 0; i < totalGroups; i++) {
        int g = groupOrder[i];
        for (int j = count[g]; j < count[g + 1]; j++) {
            ans[idx++] = bucket[j];
        }
    }

    *returnSize = n;

    free(itemOrder);
    free(groupOrder);
    free(itemHead);
    free(groupHead);
    free(itemTo);
    free(itemNext);
    free(groupTo);
    free(groupNext);
    free(itemIndeg);
    free(groupIndeg);
    free(count);
    free(pos);
    free(bucket);

    return ans;
}