C++ O(n) easy solution faster than 99.8% explained
Intuition\n Describe your first thoughts on how to solve this problem. \nUse an array to store the presence of numbers. And loop through it.\n\n# Approach\n Des
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nUse an array to store the presence of numbers. And loop through it.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1. Ceates a boolean array called `A`, where `A[i]` is true if and only if `i` is present in nums. \n2. Store a global max `maxCnt` and a local max `cnt` for the while loop. \n3. Note that We only need to iterate from 2 to 316 in the outer loop since $317^2 > 100000$, which means elements after 317 cannot form a sequence starting from it. \n4. Same for the while loop, we only need to continue the loop when `j` is less than 317.\n\n5. Note that `A[j]` can be set to `false` to speed up the performance since we have seen it and there is no need to start at `j` again. i.e. If we find `3,9,81`, it is redundant to start from `9` again.\n6. If `maxCnt < 2`, we don\'t find a valid sequence thus return -1; otherwise return `maxCnt`.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nO(n)\n\n# Code\n```\nclass Solution {\npublic:\n    int longestSquareStreak(vector<int>& nums) {\n        vector<bool> A(100001, false); \n        for (int i : nums) {\n            A[i] = true;\n        }\n\n        int maxCnt = 0, cnt, j;\n        for (int i = 2; i < 317; ++i) {  \n            cnt = 0;\n            j = i;\n            while (A[j]) {\n                ++cnt;\n                A[j] = false;\n                if (j < 317) {\n                    j *= j;\n                } else {\n                    break;\n                }\n            }\n            maxCnt = max(maxCnt, cnt);\n        }\n        \n        return maxCnt < 2 ? -1 : maxCnt;\n    }\n};\n```
['Array', 'C++']