C++ Solution for Longest Square Streak in an Array – Easy to Understand with Explanation 🟢
Intuition\n Describe your first thoughts on how to solve this problem. \n\n# Approach\nProblem:\nGiven an array of integers, the task is to find the length of t
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n# Approach\n**Problem:**\nGiven an array of integers, the task is to find the length of the longest "square streak," where a square streak is a sequence starting from an integer in the array where each subsequent number is the square of the previous one and also appears in the array.\n\n**Solution Explanation:**\n\n1. **Sort the Array**: We first sort the array to process elements in increasing order.\n2. **Store Elements in a Set**: By using an `unordered_set`, we can efficiently check if a squared number exists in the array.\n3. **Iterate Through Each Element**: For each element in the array, we initialize a `count` and start squaring the number to find a potential streak.\n4. **Update Maximum Streak Length**: For each number, we square it repeatedly and check if the result is in the set. If it is, we continue the streak; if not, we break out of the loop. We then update the maximum streak length.\n5. **Return the Result**: If a streak longer than 1 is found, return the maximum length; otherwise, return `-1`.\n\nThis approach has a time complexity of \\(O(n \\log n)\\) due to sorting, and then \\(O(n)\\) for iterating through the array and checking streaks, making it efficient for large arrays.\n\nHere\u2019s the code:\n\n```cpp\nclass Solution {\npublic:\n    int longestSquareStreak(vector<int>& nums) {\n        // Step 1: Sort the array\n        sort(nums.begin(), nums.end());\n        \n        // Step 2: Create a set to store elements for quick look-up\n        unordered_set<int> st(nums.begin(), nums.end());\n        \n        int maxi = 0; // To store the longest square streak\n        \n        // Step 3: Iterate over each element in the sorted array\n        for (int i = 0; i < nums.size(); i++) {\n            int count = 1;\n            long long number = nums[i];\n            \n            // Step 4: Attempt to create a square streak starting from the current element\n            while (true) {\n                long long val = number * number;\n                \n                // Stop if `val` exceeds INT_MAX or isn\'t found in the set\n                if (val > INT_MAX || st.find(val) == st.end()) {\n                    break;\n                }\n                \n                count++;\n                number = val; // Move to the next squared value\n            }\n            \n            // Update the maximum streak length if the current one is the longest so far\n            maxi = max(maxi, count);\n        }\n\n        // Step 5: Return the result, -1 if no valid streak is found\n        return (maxi > 1) ? maxi : -1;\n    }\n};\n```\n\n---\n\n\n\n**Why This Solution Works**:\nSorting ensures that smaller numbers come first, so if we start a streak from any number, we\u2019ve already processed smaller numbers that could start their own streaks. By checking squares within the range of `INT_MAX`, we prevent overflow issues.\n\n---\n\n**Edge Cases Considered**:\n1. **Single-element arrays**: Returns `-1` because there\u2019s no valid streak.\n2. **Arrays with no streak**: Returns `-1` if no square relationships are found.\n3. **Large arrays with high values**: Checks for overflow with `INT_MAX` to avoid errors.\n\nHope this helps! Feel free to ask questions if you have any doubts \uD83D\uDE0A\n\n# Complexity Analysis\n- **Time Complexity**: O(nlog n) due to sorting, and O(n) for iterating through each number.\n- **Space Complexity**: O(n) for the set storing elements of the array.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int longestSquareStreak(vector<int>& nums) {\n        sort(nums.begin(), nums.end());\n        unordered_set<int> st(nums.begin(), nums.end());\n        \n        int maxi = 0; \n        unordered_map<int, int> mp; \n\n        for (int i = 0; i < nums.size(); i++) {\n            int count = 1;\n            long long number = nums[i];\n\n            while (true) {\n                long long val = number * number;\n                \n                if (val > INT_MAX || st.find(val) == st.end()) {\n                    break;\n                }\n                \n                count++;\n                number = val;\n            }\n            \n            mp[nums[i]] = count; \n            maxi = max(maxi, count); \n        }\n\n        return (maxi > 1) ? maxi : -1;\n    }\n};\n\n```
['C++']