LeetCode Entry

1601. Maximum Number of Achievable Transfer Requests

2.07.2023 hard 2023 kotlin

Max edges to make all counts in == out edges in graph

1601. Maximum Number of Achievable Transfer Requests hard blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/263

Problem TLDR

Max edges to make all counts in == out edges in graph

Intuition

Let’s observe some examples: image.png

All requests are valid if count of incoming edges are equal to outcoming. One possible solution is to just check each combination of edges.

Approach

Let’s use bitmask to traverse all combinations, as total number 16 can fit in Int

Complexity

  • Time complexity: \(O(n2^r)\)

  • Space complexity: \(O(n2^r)\)

Code


fun maximumRequests(n: Int, requests: Array<IntArray>): Int =
    (0..((1 shl requests.size) - 1)).filter { mask ->
        val fromTo = IntArray(n)
        requests.indices.filter { ((1 shl it) and mask) != 0 }.forEach {
            val (from, to) = requests[it]
            fromTo[from] -= 1
            fromTo[to] += 1
        }
        fromTo.all { it == 0 }
    }.map { Integer.bitCount(it) }.max()!!