Python | 3 Solutions | DP | Union Find | While loop | Beats 100%  🚀
Intuition\n Describe your first thoughts on how to solve this problem. \nI have 3 solutions: \n\n1. Dynamic programming\n2. While loop and seen set\n3. Union Fi
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nI have 3 solutions: \n\n1. Dynamic programming\n2. While loop and seen set\n3. Union Find solution\n\n\n# Complexity\n- Time complexity:$$O(n)/ O(nlogm)$$\nwhere m=unique numbers\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n\n- Space complexity:$$O(n)$$\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n\n# Dynamic Programming Solution Beats 100%  \uD83D\uDE80\n```python3 []\n\nclass Solution:\n    def longestSquareStreak(self, nums: List[int]) -> int:\n        nums = sorted(set(nums))\n        dp={i:1 for i in nums}\n        longest=1\n        for i in nums:\n            sq= i**2\n            if sq in dp:\n                dp[sq]= dp[i]+1\n                if dp[sq]==5: return dp[sq]\n                if dp[sq]>longest:\n                    longest=dp[sq]\n        return longest if longest!=1 else -1\n        \n```\n![image.png](https://assets.leetcode.com/users/images/ebbe8410-faf8-4060-939c-24cf5e72575a_1730087994.592341.png)\n\n# Intuitive while loop solution, Calculates square and sqrt without sorting Beats 100%  \uD83D\uDE80\n```python3 []\nclass Solution:\n    def longestSquareStreak(self, nums: List[int]) -> int:\n        nums = set(nums)\n        maxcount=1\n        while(nums):\n            i= nums.pop()\n            count=1\n            sq= i**2\n            sqroot = math.sqrt(i)\n            while(sq in nums):\n                count+=1\n                nums.remove(sq)\n                sq=sq**2\n            while (sqroot in nums):\n                count+=1\n                nums.remove(sqroot)\n                sqroot = math.sqrt(sqroot)\n            if count==5: return count\n            elif count>maxcount:\n                maxcount= count        \n        return maxcount if maxcount>1 else -1       \n```\n![image.png](https://assets.leetcode.com/users/images/cc3d7f94-cd4a-488f-849f-b092a69c4b4a_1730087856.8111742.png)\n\n\n# Union Find solution Beats 100%  \uD83D\uDE80\n```python3 []\nclass UnionFind():\n    def __init__(self):\n        self.rank={}\n        self.parent = {}\n        self.maxrank = 0\n    \n    def add(self, node):\n        self.parent[node] = node\n        self.rank[node]=1\n    \n    def find(self, n1):\n        if self.parent[n1]!=n1:\n            self.parent[n1] = self.find(self.parent[n1])\n        return self.parent[n1]\n    \n    def union (self, n1, n2):\n        p1, p2= self.find(n1), self.find(n2)\n        if p1==p2:\n            return \n        if self.rank[p1]>self.rank[p2]:\n            self.parent[p2]=p1\n            self.rank[p1]+=self.rank[p2]\n            if self.rank[p1]> self.maxrank:\n                self.maxrank =  self.rank[p1]\n        else:\n            self.parent[p1]=p2\n            self.rank[p2]+=self.rank[p1]\n            if self.rank[p2]> self.maxrank:\n                self.maxrank =  self.rank[p2]        \n        if self.maxrank ==5:\n            return 5\nclass Solution:\n    def longestSquareStreak(self, nums: List[int]) -> int:\n        nums= set(nums)\n        uf = UnionFind()\n        for i in nums:\n            sq=i**2\n            if sq in nums:\n                if i not in uf.parent:\n                    uf.add(i)\n                if sq not in uf.parent:\n                    uf.add(sq)\n                if uf.union(i, sq):\n                    return 5\n        return uf.maxrank if uf.maxrank!=0 else -1\n```\n\n![image.png](https://assets.leetcode.com/users/images/a37118c9-05d8-4758-b413-ea751d388b1b_1730087919.2686207.png)\n
['Hash Table', 'Dynamic Programming', 'Union Find', 'Ordered Set', 'Python3']