Problem statement

https://binarysearch.com/problems/Chain-of-Blocks/

Solution

Actually what is asked is to find the longest path in DAG, we can do it with dp.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, blocks):
        G = defaultdict(list)
        for x, y in blocks:
            G[y] += [x]

        @lru_cache(None)
        def dp(x):
            if not G[x]: return 0
            return max([dp(y) for y in G[x]]) + 1

        keys = list(x for x in G)
        if not keys: return 0
        return max(dp(a) for a in keys)