LeetCode Entry

1203. Sort Items by Groups Respecting Dependencies

20.08.2023 hard 2023 kotlin

Sort items by groups and in groups given dependencies.

1203. Sort Items by Groups Respecting Dependencies hard blog post substack

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/314

Problem TLDR

Sort items by groups and in groups given dependencies.

Intuition

Use hint.

We can split items by groups and check groups dependencies. Next, do Topological Sort for groups and then do Topological Sort for items in each group.

Approach

Now, the tricks:

• if we consider each -1 as a separate group, code will become cleaner
• we don’t have to do separate Topological Sort for each group, just sort whole graph of items, then filter by each group
• cycle detection can be done in a Topological Sort: if there is a cycle, there is no item with indegree == 0
• Topological Sort function can be reused

Complexity

• Time complexity: \(O(nm + E)\)

• Space complexity: \(O(n + n + E)\)

Code

    class G(count: Int, val fromTo: MutableMap<Int, MutableSet<Int>> = mutableMapOf()) {
      operator fun get(k: Int) = fromTo.getOrPut(k) { mutableSetOf() }
      val order: List<Int> by lazy {
        val indegree = IntArray(count)
        fromTo.values.onEach { it.onEach { indegree[it]++ } }
        val queue = ArrayDeque<Int>(indegree.indices.filter { indegree[it] == 0 })
        generateSequence { queue.poll() }
            .onEach { fromTo[it]?.onEach { if (--indegree[it] == 0) queue += it } }
            .toList().takeIf { it.size == count } ?: listOf()
      }
    }
    fun sortItems(n: Int, m: Int, group: IntArray, beforeItems: List<List<Int>>): IntArray {
      var groupsCount = m
      for (i in 0 until n) if (group[i] == -1) group[i] = groupsCount++
      val items = G(n)
      val groups = G(groupsCount)
      for (to in beforeItems.indices)
        for (from in beforeItems[to])
          if (group[to] == group[from]) items[from] += to
          else groups[group[from]] += group[to]
      return groups.order.flatMap { g -> items.order.filter { group[it] == g } }.toIntArray()
    }