Longest chain in a graph. O(n) time & O(n) space regardless of arbitrarily large input values.
Intuition\nWe can create a graph where each node points to its square if that square exists in the input. The solution is then the number of nodes in the longes
# Intuition\nWe can create **a graph where each node points to its square** if that square exists in the input. The solution is then the number of nodes in the **longest chain in the graph**.\n\nThis graph in practice ends up being **a set of linked lists**. That is because, for all positive integers `n` and `m`, if `n != m` then `pow(n, 2) != pow(m, 2)` and vice versa.\n\nNotice that we don\'t need to sort the input since regardless of the order that we create the edges in our graph the end result will be the same and we do all our processing after the graph is fully constructed.\n\n# Approach\nWe can use a set to quickly check if the square exists for each number in the input and construct the edges of the graph accordingly. Once the graph is fully constructed, we can recursively calculate the length of the chain starting at each node. By caching the result of the recursion (Dynamic Programming) we will only need to visit each node once. We return the length of the longest chain we found unless it is less than `2` in which case we return `-1` because the problem statement does not consider that to be a "square streak".\n\n# Complexity\n\n### Time complexity:\nWe check for the square of each node while constructing the graph, which takes *O(n)*.\nWe then find the length of the longest chain the graph which takes *O(n)* as well since we are only visiting each node once thanks to recursive dynamic programming.\nOur total time complexity is then *O(n)* + *O(n)* = ***O(n)***.\n\n### Space complexity:\nThere are three sources of memory usage:\n- The set used to check for squares\n- The graph\n- The cache used for dynamic programming\n\nAll three use *O(n)* space, so the total space complexity is ***O(n)***.\n\n# Code\n```python3 []\nclass Solution:\n    def longestSquareStreak(self, nums: List[int]) -> int:\n        num_set = set(nums)\n\n        graph = dict()  # Each element points to its square if it exists\n        for n in nums:\n            square = n**2\n            if square in num_set:\n                graph[n] = square\n\n        @cache\n        def get_length(n):\n            if n in graph:\n                return 1 + get_length(graph[n])\n            elif n in num_set:\n                return 1\n            else:\n                return 0\n\n        longest_streak = max(map(get_length, nums))\n        return longest_streak if longest_streak >= 2 else -1\n\n```
['Python3']