C++ using array hashing easy to understand
Intuition\nOur task is to form a progression where each number is the square of the previous one, we need to find the longest chain of numbers where each elemen
# Intuition\nOur task is to form a progression where each number is the square of the previous one, we need to find the longest chain of numbers where each element is the square of the preceding one. A straightforward but inefficient approach would involve looping through the array and, for each number, searching for its square in the remaining array. The longest sequence found this way would be our desired "square streak."\n\nHowever, performing a linear search across the entire array is too slow. To optimize, we can use a boolean array as a presence map, with a fixed size of (10^5) (the maximum possible value). This map allows us to check if an element is present by looking up the corresponding index: if the value is `1`, it\u2019s present; if `0`, it\u2019s absent.\n\nFor each test case, though, a fixed-size array of (10^5) would waste memory. Instead, we can optimize by setting the size of the array to `maxValue + 1`, where `maxValue` is the largest number in `nums`. This way, our presence map only covers the range necessary for each test case, balancing both efficiency and memory usage.\n<!-- Describe your first thoughts on how to solve this problem. -->\n\n \n<!-- Describe your approach to solving the problem. -->\n# Complexity\n- Time complexity: `O(N)`\nThe time complexity of the std::max_element function in C++ is `O(N)`\nThe Initialization of vector takes `O(N)`\nThe for loop that itrates over the numbers in nums takes `O(N)`\nFor each number it checks a sequence of squares until either the square reaches the `maxValue` making it `O(1)` making the effective time complexity of the main Loop to be `O(1)*O(N)` which is effectively `O(N)`\nThe overall time complexity becomes `O(N) + O(N) + O(N) + O(N)`\nwhich simplifies to ` O(N)`\n<!-- Add your time complexity here, e.g. $$O(N)$$ -->\n\n- Space complexity: `O(N)`\nLet\'s break down the space complexity for each component in the code:\n**`maxValue`**: This is a single integer, so it requires `O(1)` space.\n**`valuesMap`**: This is a boolean vector of size `maxValue + 1`. If the maximum element in `nums` is N, the vector will have (N + 1) elements, So it requires `O(N)` space.\n**`streak`**: This is also a single integer, so it requires `O(1)` space.\nThe overall time complexity becomes `O(1) + O(N) + O(1)`\nwhich simplifies to ` O(N)`\n<!-- Add your space complexity here, e.g. $$O(N)$$ -->\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int longestSquareStreak(vector<int>& nums) {\n\n        int maxValue = *max_element(nums.begin(),nums.end());\n        vector<bool>valuesMap(maxValue+1,0);\n\n        for(int& num:nums){\n            valuesMap[num]=1;\n        }\n\n        int streak = 0;\n\n        for(int& num:nums){\n            int curStreak = 0;\n            long long cur = num;\n\n            while(valuesMap[(int) cur]){\n                curStreak++;\n                if(cur*cur > maxValue){\n                    break;\n                }\n                cur*=cur;\n            }\n            streak = max(streak,curStreak);\n        }\n\n        return streak<2?-1:streak;\n    }\n};\n```
['Array', 'Hash Table', 'C++']