Problem statement

https://leetcode.com/problems/array-nesting/

Solution

Actually, what we have is permutation of numbers, where we need to find the longest loop. What we need to do is to look at our nums as graph, imagine we have nums = [5, 4, 0, 3, 1, 6, 2], then we have connections: 0 -> 5, 1 -> 4, 2 -> 0, 3 -> 3, 4 -> 1, 5 -> 6, 6 -> 2, which in fact can be looked as several disjoint loops 0 -> 5 -> 6 -> 2 -> 0, 1 -> 4 -> 1, 3 -> 3.

So, we start from value 0 and start to traverse our graph. We will keep already visited nodes in visited set, so if we already traversed some loop, we never do it again: it is very similar what we do in classical dfs algorithm when we want to find islands.

Complexity

Time and space complexity is O(n), because we never visit node twice.

Code

class Solution:
    def arrayNesting(self, nums):
        n = len(nums)
        visited = [0]*n
        for i in range(n):
            start, depth = i, 1
            while not visited[start]:
                visited[start] = depth
                start = nums[start]
                depth += 1
                
        return max(visited)

Remark

Can we do better? Not in time: we need to look at our data at least once, what about space? We can also rewrite original array with -1 with O(n) time and O(1) space. Finally, if we are not allowed to modify data, we can use loop detection technique with slow and fast iterators with O(n) time and O(1) memory.