[Python] loop detection, explained
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 nu
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`.\n\nSo, 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.\n\n#### Complexity\nTime and space complexity is `O(n)`, because we never visit node twice.\n\n#### Code\n```python\nclass Solution:\n    def arrayNesting(self, nums):\n        n = len(nums)\n        visited = [0]*n\n        for i in range(n):\n            start, depth = i, 1\n            while not visited[start]:\n                visited[start] = depth\n                start = nums[start]\n                depth += 1\n                \n        return max(visited)    \n```\n\n#### Remark\nCan 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.\n\nIf you have any questions, feel free to ask. If you like solution and explanations, please **Upvote!**
[]