Easy solution using Hash Table for "Longest Square Streak in Array"
\n# Longest Square Streak Problem\n\n## Intuition\nTo solve this problem, we aim to find the longest sequence of numbers where each successive number in the seq
\n# Longest Square Streak Problem\n\n## Intuition\nTo solve this problem, we aim to find the longest sequence of numbers where each successive number in the sequence is the square of the previous one. Observing that the numbers need to be sorted and processed only when they fit within bounds provides an efficient way to handle the problem. We keep track of counts using a hash table to facilitate easy access and counting of each number.\n\n## Approach\n1. **Sorting**: Start by sorting the array, which ensures that each number is processed in increasing order.\n2. **Hash Table for Frequency**: Store the frequency of each number in a hash table to track each occurrence and allow marking numbers as used without additional data structures.\n3. **Iterate and Count Streaks**: For each number in the sorted list:\n   - Initialize a count for the streak (`ans`), starting with the current number.\n   - Follow the sequence by continually squaring the current number and checking if it exists in the hash table and falls within bounds.\n   - Continue until the squared number exceeds the limit or is unavailable.\n4. **Update Maximum Streak**: Track the longest streak found and return it if it\u2019s greater than 1; otherwise, return -1.\n\n## Complexity\n\n- **Time Complexity**:  \n  $$O(n \\log n)$$ due to sorting, where $$n$$ is the number of elements in `nums`.\n  \n- **Space Complexity**:  \n  $$O(n)$$ for storing the hash table of frequencies.\n\n## Code\n```cpp\nclass Solution {\npublic:\n    int longestSquareStreak(vector<int>& nums) {\n        sort(nums.begin(), nums.end());\n        int hash[100001] = {0};\n        \n        for (int i = 0; i < nums.size(); i++) {\n            hash[nums[i]]++;\n        }\n        \n        int cnt = 0;\n        \n        for (int i = 0; i < nums.size(); i++) {\n            int current = nums[i];\n            int temp = 0;\n            \n            while (current <= 100000 && hash[current] > 0) {\n                temp++;\n                hash[current]--;\n                \n                long long nextSquare = (long long)current * current;\n                if (nextSquare > 100000) break;\n                \n                current = nextSquare;\n            }\n            \n            cnt = max(cnt, temp);\n        }\n        \n        return (cnt > 1 ? cnt : -1);\n    }\n};\n```\n
['Array', 'Hash Table', 'Sorting', 'C++']