💡 C++ | O(nLogn) | Beginner Solution | Simple Logic | With Full Explanation ✏️
Intuition\nTo find the longest streak where each number can be squared to get the next number in the sequence, we can leverage a sorted list and a hash map. The
# Intuition\nTo find the longest streak where each number can be squared to get the next number in the sequence, we can leverage a sorted list and a hash map. The sorted list allows us to start with the smallest numbers and try to build streaks by squaring them. Using a hash map for quick lookups ensures that we can efficiently check if the squared result exists in `nums`.\n\n# Approach\n1. **Sort the Array:** Sorting helps us to process numbers from smallest to largest, making it easier to find streaks that start with the smallest base number.\n\n2. **Store Frequencies in Hash Map:** Use a hash map (`mpp`) to store the frequency of each element in nums. This allows constant-time lookups to check if a squared number exists in the original array.\n\n3. **Iterate through Each Element:** For each number in the sorted nums array, treat it as the starting point of a potential square streak.\n\n    - Initialize a counter (`cnt`) to keep track of the streak length.\n    - Use a loop to repeatedly square the current number. If the squared value exists in `mpp`, increment the streak count (`cnt`). If the squared number is not found in the hash map, the streak ends for this starting point.\n4. Update the Longest Streak: After ending each streak, update `ans` with the maximum streak length encountered.\n\n5. Return the Result: After processing all elements, `ans` holds the longest streak length where each number in the streak can be squared to get the next. If no valid streak was found, `ans` will return -1.\n\n# Complexity\n- Time complexity:\n```O(nLogn)```\n\n- Space complexity:\n```O(n)```\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int longestSquareStreak(vector<int>& nums) {\n        int ans = -1; // Variable to store the maximum streak length\n        unordered_map<int, int> mpp; // Hash map to count occurrences \n        sort(nums.begin(), nums.end()); \n        for (int i : nums) {\n            mpp[i]++;\n        }\n        for (int i = 0; i < nums.size(); i++) {\n            long num = nums.at(i);\n            int cnt = 0; // Variable to count the streak length \n            // Continue multiplying num by itself until it exceeds the largest number in nums\n            while (num <= nums.at(nums.size() - 1)) {\n                num *= num; \n                \n                // If the squared value is not found in the map, break the streak\n                if (mpp[num] == 0) {\n                    if (cnt != 0) { // Update ans if a streak has been counted\n                        cnt++; // Increment the streak count for the current number\n                        ans = max(ans, cnt); // Update the max streak length\n                    }\n                    break; \n                } else {\n                    cnt++; // Increment the streak count if squared value exists in the map\n                }\n            }\n        }\n        \n        return ans; \n    }\n};\n\n```\n\n\n\n![anonupvote.jpeg](https://assets.leetcode.com/users/images/bf7ce48f-1a34-404c-8610-410d43112c2c_1720413559.1746094.jpeg)\n\n# Ask any doubt !!!\nReach out to me \uD83D\uDE0A\uD83D\uDC47\n\uD83D\uDD17 https://tushar-bhardwaj.vercel.app/
['C++']