C# Solution for Longest Square Streak In An Array Problem
Intuition\n Describe your first thoughts on how to solve this problem. \nThe goal is to find the longest subsequence in nums where each successive element is th
# Intuition\n<!-- Describe your first thoughts on how to solve this problem. -->\nThe goal is to find the longest subsequence in nums where each successive element is the square of the previous one. Since a valid subsequence must follow this \u201Csquared\u201D relationship, we need to be able to quickly check if each squared number exists in the array\n\n# Approach\n<!-- Describe your approach to solving the problem. -->\n1.\tUnique Element Storage: Use a HashSet to store all unique elements from nums, allowing for efficient O(1) lookups to check if the next number in a potential square streak exists.\n2.\tIterate Through Each Element: Treat each element in nums as a potential starting point of a square streak.\n\t\u2022\tInitialize currentStreak to count the streak length and current to track the current number.\n\t\u2022\tFor each starting element, try to build a square streak by repeatedly squaring current and checking if it exists in uniqueNumbers.\n\t\u2022\tConstraint Check: If current * current exceeds 10^5, stop extending the streak to avoid overflow and respect problem constraints.\n3.\tUpdate Longest Streak: After attempting a streak from each starting point, update longestStreak if the current streak is the longest seen so far.\n4.\tReturn Result: If longestStreak is less than 2, return -1 (indicating no valid streak); otherwise, return longestStreak.\n\n# Complexity\n- Time complexity:\n<!-- Add your time complexity here, e.g. $$O(n)$$ -->\n1.\tBuilding the HashSet: This requires O(n) time, where n is the length of nums.\n2.\tIterating Through Each Element:\n\t\u2022\tFor each element x in nums, we attempt to build a streak by squaring current until it exceeds 10^5 or can no longer be found in the set.\n\t\u2022\tThe number of times we can square a number before it exceeds 10^5 is logarithmic in growth, specifically O(log(log x)).\n\t\u2022\tOverall, due to this limit on streaks, the amortized complexity remains close to O(n), even though we repeatedly square numbers within a limited range.\n3.\tTotal Complexity: O(n).\n\n- Space complexity:\n<!-- Add your space complexity here, e.g. $$O(n)$$ -->\n1.\tHashSet Storage: The HashSet uses O(n) space to store all unique elements in nums.\n2.\tAuxiliary Variables: Minimal additional space is used for variables like currentStreak and current.\n\nOverall Space Complexity: O(n).\n\n# Code\n```csharp []\npublic class Solution {\n    public int LongestSquareStreak(int[] nums) {\n        int longestStreak = 0;\n\n        // Create a HashSet to store all unique numbers from the input array\n        HashSet<int> uniqueNumbers = new HashSet<int>(nums);\n\n        // Iterate through each number in the input array\n        foreach (int startNumber in nums) {\n            int currentStreak = 0;\n            long current = startNumber;\n\n            // Continue the streak as long as we can find the next square in the set\n            while (uniqueNumbers.Contains((int)current)) {\n                currentStreak++;\n                \n                // Break if the next square would be larger than 10^5 (problem constraint)\n                current *= current;\n                if (current > 100000) break;\n            }\n\n            // Update the longest streak if necessary\n            longestStreak = Math.Max(longestStreak, currentStreak);\n        }\n\n        // Return -1 if no valid streak found, otherwise return the longest streak\n        return longestStreak < 2 ? -1 : longestStreak;\n    }\n}\n```
['C#']