Find max comp size using DSU | O(N)
Intuition\nWhile Traversing the array we store the value mapped to its index in an unorderd map\nWhenever we see a number, we find its\nsquare root,\nsquare\nIf
# Intuition\nWhile Traversing the array we store the value mapped to its index in an unorderd map\nWhenever we see a number, we find its\nsquare root,\nsquare\nIf we have seen any of the above before, we connect both the indices\nAt the end we just need to return the largest component in the dsu.\n\n# Approach\nDSU + Traversal\n\n# Complexity\n\n- Time complexity:\n\nO(N)\nSince in DSU, we can do union in almost constant time, So the time complexity is O(N)\n\n\n\n- Space complexity:\n\nO(N)\nTo store the DSU array of parent and size and the unordered map\n\n\n\n# Code\n```cpp []\nstruct _dsu{\n    vector <int> _parent;\n    vector <int> _size;\n\n    _dsu(int n){\n        _parent.resize(n);\n        for( int i = 0 ; i < n ; i++ ){\n            _parent[i] = i;\n        }\n\n        _size.resize(n,1);\n    }\n\n    int _find(int n){\n        if( _parent[n] == n )\n            return n;\n        return _parent[n] = _find(_parent[n]);\n    }\n\n    void _union(int a,int b){\n        a = _find(a);\n        b = _find(b);\n        if( a == b )\n            return;\n        if( _size[a] < _size[b])\n            swap(a,b);\n        \n        _parent[b] = a;\n        _size[a] += _size[b];   \n    }\n\n    int maxComp(){\n        return *max_element(_size.begin(), _size.end());\n    }\n};\n\nclass Solution {\npublic:\n    int longestSquareStreak(vector<int>& nums) {\n        int n = nums.size();\n        _dsu dsu = _dsu(n);\n        unordered_map <long long,int> mpp;\n\n        for( int i = 0 ; i < n ; i++ ){\n            if( mpp.count(nums[i]))\n                continue;\n            long long x = nums[i];\n            long long sq = x*x;\n            long long rt = sqrt(x);\n            if( mpp.count(sq) > 0 ){\n                dsu._union(i, mpp[sq]);\n            }\n            if( rt*rt == x && mpp.count(rt) > 0 ){\n                dsu._union(i, mpp[rt]);\n            }\n            mpp[x] = i;\n        }\n        int ans = dsu.maxComp();\n        return ans > 1 ? ans : -1;\n    }\n};\n```
['Union Find', 'Graph', 'C++']