BinarySearch 0619 Separate Predators

Problem statement

https://binarysearch.com/problems/Separate-Predators/

Solution

We need to find the longest path in graph, we can always go to the parent and use memoisation.

Complexity

It is O(n) for time and space.

Code

class Solution:
    def solve(self, A):
        @lru_cache(None)
        def dfs(i):
            if A[i] == -1: return 1
            return dfs(A[i]) + 1

        return max(dfs(i) for i in range(len(A)))