Chasing Squares: Finding the Longest Square Streak in an Array!
Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal is to find the longest "square streak," where a sequence of elements in the ar
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal is to find the longest "square streak," where a sequence of elements in the array each is a square of the previous one. The initial thought is to use a Set for constant-time membership checking, allowing us to verify each squared element\'s presence efficiently.\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\nStep1: Add all elements from nums into a Set for quick lookup.\nStep2: For each unique element in the set, try to build a streak by repeatedly squaring the element and checking if the result exists in the set.\nStep3: Track the longest streak found. Use a long type to avoid overflow when squaring.\nStep4: Return the longest streak, or -1 if the maximum streak length is 1.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\nO(n\u22C5logm)\nwhere\nn is the number of unique elements and \nm is the largest element. Each element might be squared multiple times until it exceeds Integer.MAX_VALUE.\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\nfor storing the elements in a Set\n\n# Code\n```java []\nclass Solution {\n    public int longestSquareStreak(int[] nums) {\n        Set<Integer> s= new LinkedHashSet<>();\n        for(int i: nums) s.add(i);\n        List<Integer> l= new ArrayList<>(s);\n        long lon=0;\n        for(int i=0; i<l.size(); i++){\n            int lo=1;\n            long ele= l.get(i);\n            while(ele*ele<= Integer.MAX_VALUE && s.contains((int)(ele*ele))){\n                ele= ele*ele;\n                lo+=1;\n            }\n            lon= Math.max(lon, lo);\n        }\n        return lon==1? -1: (int)lon;\n    }\n}\n```
['Java']