Maximum Number of Achievable Transfer Requests LeetCode solution in Python

1
# Runtime: 4533 ms (Top 17.14%) | Memory: 13.9 MB (Top 48.57%)
2
class Solution:
3
    def maximumRequests(self, n: int, r: List[List[int]]) -> int:
4
        k = len(r)
5
        deg = [0 for i in range(n)]
6

7
        def check(i, res, s):
8
            if i == k:
9
                # print(deg,s)
10
                if max(deg) == min(deg) == 0:
11
                    res[0] = max(res[0], s)
12
                return
13

14
            u, v = r[i]
15
            deg[u] -= 1
16
            deg[v] += 1
17
            check(i + 1, res, s + 1)
18
            deg[u] += 1
19
            deg[v] -= 1
20
            check(i + 1, res, s)
21

22
        res = [0]
23
        check(0, res, 0)
24
        return res[0]