Best Solution Ever ❤️‍🔥❤️‍🔥!!!! Done ✅ !!!! No Sorting !!!! Easy Solution ✅ !!!!
Intuition\nThe problem requires us to find the longest "square streak" in the input array. A "square streak" is a sequence of numbers where each number is the s
# Intuition\nThe problem requires us to find the longest "square streak" in the input array. A "square streak" is a sequence of numbers where each number is the square of the previous one, starting from a number in the array.\n\n**The main idea is to:**\n- **Identify Starting Points:** For each number in the array, check if it can be the start of a square streak. We don\u2019t want to start from a number that is already a square of another number in the array, as that would be in the middle of a streak, not the start.\n- **Track and Count Streaks:** For each valid starting point, multiply it repeatedly by itself to see how many times you can continue this sequence within the set.\n- **Update the Maximum Streak:** Keep track of the maximum streak length encountered during the process.\n\n# Approach\n- **Store Elements in a Set:** First, insert all elements in an unordered set `(unordered_set)` for efficient lookup. This allows us to quickly check if the next number in a streak exists in the array.\n\n- **Iterate Over Each Number:** For each number in the array, check if it could be the beginning of a streak by confirming that its square root does not exist in the set (`st.find(sqrt(num)) == st.end()`).\n\n- **Count the Streak:** If it\u2019s a valid starting point, keep squaring the number and counting the streak length while each squared value is still in the set. To avoid overflow, break the loop if the squared number exceeds `INT_MAX`.\n\n- **Update the Answer:** Update the answer with the maximum streak length. If no streak of length 2 or more is found, return `-1`.\n\n# Complexity\n- Time complexity:\n1. **Initialization of the unordered_set**: The construction of the unordered_set from the vector `nums` takes O(n) time, where n is the number of elements in `nums`.\n\n2. **Outer loop**: The outer loop iterates over each element in `nums`, which takes O(n) time.\n\n3. **Inner while loop**: For each number in `nums`, the inner while loop checks if the current number (starting from `num` and then squaring it) exists in the set. In the worst case, this loop could run multiple times, but since the numbers grow exponentially (squaring), the number of iterations is limited. Specifically, the number of times you can square a number before it exceeds INT_MAX is logarithmic in relation to the size of the number. Therefore, the inner loop can be considered to run O(log m) times, where m is the maximum value in `nums`.\n\nCombining these, the overall time complexity can be approximated as `O(n log m)`.\n\n- **Space complexity:**\nThe space complexity is primarily determined by the unordered_set, which stores all unique elements from `nums`. Therefore, the space complexity is O(n) in the worst case, where all elements in `nums` are unique.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int longestSquareStreak(vector<int>& nums) {\n        unordered_set<long long> st(nums.begin(), nums.end());\n\n        int ans = 0;\n        for (int num : nums) {\n            int count = 0;\n            long long curr = num;\n            while (st.find(curr) != st.end()) {\n                count++;\n                curr = curr * curr;\n                if (curr > INT_MAX) break;  // Avoid overflow\n            }\n            ans = max(ans, count);\n        }\n        return ans >= 2 ? ans : -1;\n    }\n};\n\n```\n```Java []\nimport java.util.HashSet;\nimport java.util.Set;\n\nclass Solution {\n    public int longestSquareStreak(int[] nums) {\n        Set<Long> set = new HashSet<>();\n        for (int num : nums) {\n            set.add((long) num);\n        }\n\n        int maxStreak = 0;\n        for (int num : nums) {\n            int count = 0;\n            long current = num;\n            while (set.contains(current)) {\n                count++;\n                current = current * current;\n                if (current > Integer.MAX_VALUE) break; // Avoid overflow\n            }\n            maxStreak = Math.max(maxStreak, count);\n        }\n\n        return maxStreak >= 2 ? maxStreak : -1;\n    }\n}\n```\n```Python []\nclass Solution:\n    def longestSquareStreak(self, nums):\n        num_set = set(nums)\n        max_streak = 0\n        \n        for num in nums:\n            count = 0\n            current = num\n            while current in num_set:\n                count += 1\n                current = current * current\n                if current > 2**31 - 1:  # Avoid overflow (INT_MAX equivalent)\n                    break\n            max_streak = max(max_streak, count)\n        \n        return max_streak if max_streak >= 2 else -1\n\n```\n```JavaScript []\nvar longestSquareStreak = function(nums) {\n    const set = new Set(nums.map(num => BigInt(num)));\n    let maxStreak = 0;\n\n    for (let num of nums) {\n        let count = 0;\n        let current = BigInt(num);\n        while (set.has(current)) {\n            count++;\n            current *= current;\n            if (current > BigInt(Number.MAX_SAFE_INTEGER)) break; // Avoid overflow\n        }\n        maxStreak = Math.max(maxStreak, count);\n    }\n\n    return maxStreak >= 2 ? maxStreak : -1;\n};\n```
['Array', 'Hash Table', 'Binary Search', 'Dynamic Programming', 'Sorting', 'C++', 'Java', 'Python3', 'JavaScript']