2 Methods || JAVA C++ PYTHON.
BOISS JUST UPVOTE , I WORK SO HARD WRITNG THIS OUT AND YOU SHAMELESS PEOPLE DONT EVEN LIKE THE POST . PLS UPVOTE IT.\n\n\n# M1:) ---> O(NLOGN) SORT+BINARY+DP (m
# BOISS JUST UPVOTE , I WORK SO HARD WRITNG THIS OUT AND YOU SHAMELESS PEOPLE DONT EVEN LIKE THE POST . PLS UPVOTE IT.\n\n\n# M1:) ---> O(NLOGN) SORT+BINARY+DP (memoization).\n\n\n**1. Sorting the Array:**\n   - The `nums` array is sorted in ascending order. This helps in using binary search to efficiently find the square of a number in the array.\n\n**2. Dynamic Programming:**\n   - A `dp` array is used to memoize the length of the longest square streak starting from each index.\n   - The `solve` function recursively calculates the length of the square streak for a given index.\n   - If the result for the current index is already stored in the `dp` array, it is returned directly.\n   - The square of the current number is calculated using `long` multiplication to avoid potential integer overflow.\n   - Binary search is used to find the index of the square in the sorted array. If found, the `maxStreak` is incremented by the result of the recursive call on the next index.\n   - The calculated `maxStreak` is stored in the `dp` array for future reference.\n\n**3. Finding the Maximum Streak:**\n   - The `maxStreak` variable is initialized to 0.\n   - The `solve` function is called for each index in the sorted array.\n   - The maximum `maxStreak` value is updated after each call.\n\n```java []\nclass Solution {\n    public int longestSquareStreak(int[] nums) {\n        Arrays.sort(nums); // Step 1: Sort the array\n        int n = nums.length;\n        int[] dp = new int[n]; // Step 2: Memoization array\n        int maxStreak = 0;\n\n        for (int i = 0; i < n; i++) {\n            maxStreak = Math.max(maxStreak, solve(i, nums, dp));\n        }\n\n        return maxStreak > 1 ? maxStreak : -1; // If no valid streak, return -1\n    }\n\n    private int solve(int index, int[] nums, int[] dp) {\n        if (dp[index] != 0) {\n            return dp[index]; // Use memoized result\n        }\n\n        long square = (long) nums[index] * nums[index]; // Calculate square\n        int maxStreak = 1; // Initialize streak length to 1\n\n        // Use binary search to find the square in the sorted array\n        int nextIndex = binarySearch(nums, square);\n        if (nextIndex != -1) {\n            maxStreak += solve(nextIndex, nums, dp); // Extend the streak\n        }\n\n        dp[index] = maxStreak; // Memoize the result\n        return maxStreak;\n    }\n\n    // Helper method to perform binary search for a target value\n    private int binarySearch(int[] nums, long target) {\n        int left = 0, right = nums.length - 1;\n        while (left <= right) {\n            int mid = left + (right - left) / 2;\n            if (nums[mid] == target) {\n                return mid;\n            } else if (nums[mid] < target) {\n                left = mid + 1;\n            } else {\n                right = mid - 1;\n            }\n        }\n        return -1; // Target not found\n    }\n}\n```\n```python []\nclass Solution:\n    def longestSquareStreak(self, nums: List[int]) -> int:\n        nums.sort()  # Step 1: Sort the array\n        n = len(nums)\n        dp = [0] * n  # Step 2: Memoization array\n        max_streak = 0\n\n        def solve(index):\n            if dp[index] != 0:\n                return dp[index]  # Use memoized result\n\n            square = nums[index] * nums[index]  # Calculate square\n            max_streak = 1  # Initialize streak length to 1\n\n            next_index = binary_search(nums, square)  # Find the square in the array\n            if next_index != -1:\n                max_streak += solve(next_index)  # Extend the streak\n\n            dp[index] = max_streak  # Memoize the result\n            return max_streak\n\n        def binary_search(nums, target):\n            left, right = 0, len(nums) - 1\n            while left <= right:\n                mid = left + (right - left) // 2\n                if nums[mid] == target:\n                    return mid\n                elif nums[mid] < target:\n                    left = mid + 1\n                else:\n                    right = mid - 1\n            return -1  # Target not found\n\n        for i in range(n):\n            max_streak = max(max_streak, solve(i))\n\n        return max_streak if max_streak > 1 else -1  # If no valid streak, return -1\n```\n```C++ []\nclass Solution {\npublic:\n    int longestSquareStreak(std::vector<int>& nums) {\n        std::sort(nums.begin(), nums.end());  // Step 1: Sort the array\n        int n = nums.size();\n        std::vector<int> dp(n, 0);  // Step 2: Memoization array\n        int maxStreak = 0;\n\n        for (int i = 0; i < n; ++i) {\n            maxStreak = std::max(maxStreak, solve(i, nums, dp));\n        }\n\n        return maxStreak > 1 ? maxStreak : -1;  // If no valid streak, return -1\n    }\n\nprivate:\n    int solve(int index, const std::vector<int>& nums, std::vector<int>& dp) {\n        if (dp[index] != 0) return dp[index];  // Use memoized result\n\n        long long square = (long long)nums[index] * nums[index];  // Calculate square\n        int maxStreak = 1;  // Initialize streak length to 1\n\n        int nextIndex = binarySearch(nums, square);  // Find the square in the array\n        if (nextIndex != -1) {\n            maxStreak += solve(nextIndex, nums, dp);  // Extend the streak\n        }\n\n        dp[index] = maxStreak;  // Memoize the result\n        return maxStreak;\n    }\n\n    // Helper method to perform binary search\n    int binarySearch(const std::vector<int>& nums, long long target) {\n        int left = 0, right = nums.size() - 1;\n        while (left <= right) {\n            int mid = left + (right - left) / 2;\n            if (nums[mid] == target) return mid;\n            else if (nums[mid] < target) left = mid + 1;\n            else right = mid - 1;\n        }\n        return -1;  // Target not found\n    }\n};\n```\n\n\n\n\n\n\n\n\n# M2:)  ---> O(N) -> HASHSET.\n\n**1. HashSet Initialization:**\n\n- A HashSet `hs` is created to efficiently check if a number exists in the array.\n\n**2. Main Loop:**\n\n- The code iterates through each number `num` in the array.\n- For each `num`, the `dp` function is called to calculate the length of the square streak starting from that number.\n- The `maxStreak` variable is updated with the maximum streak length found so far.\n\n**3. `dp` Function:**\n\n- The `dp` function recursively calculates the length of the square streak starting from a given number `num`.\n- A `streak` variable is initialized to 0.\n- While the current `num` is in the HashSet:\n  - The `streak` is incremented.\n  - The square of `num` is calculated. To avoid potential integer overflow, the calculation is done using `long` multiplication.\n  - If the squared value exceeds the maximum integer value, the function returns the current `streak`.\n  - The `num` is updated to the squared value (safely cast back to `int`).\n- The final `streak` is returned.\n\n\n\n\n# Code\n```java []\nclass Solution {\n    HashSet<Integer> hs = new HashSet<>();\n\n    public int longestSquareStreak(int[] nums) {\n        for (int num : nums) {\n            hs.add(num);\n        }\n        int maxStreak = 0;\n\n        for (int num : nums) {\n            maxStreak = Math.max(maxStreak, dp(num));\n        }\n        return maxStreak > 1 ? maxStreak : -1;\n    }\n\n    private int dp(int num) {\n        int streak = 0;\n\n        while (hs.contains(num)) {\n            streak++;\n            long value = (long) num * num;  // Use long multiplication\n\n            if (value > Integer.MAX_VALUE) {\n                return streak;  // Break if the value overflows\n            }\n\n            num = (int) value;  // Safely cast the result back to int\n        }\n        return streak;\n    }\n}\n\n```\n```C++ []\nclass Solution {\npublic:\n    int longestSquareStreak(std::vector<int>& nums) {\n        std::unordered_set<int> hs(nums.begin(), nums.end());\n        int maxStreak = 0;\n\n        for (int num : nums) {\n            maxStreak = std::max(maxStreak, dp(num, hs));\n        }\n        return maxStreak > 1 ? maxStreak : -1;\n    }\n\npublic:\n    int dp(int num, std::unordered_set<int>& hs) {\n        int streak = 0;\n\n        while (hs.count(num)) {\n            streak++;\n            long long value = (long long)num * num;\n\n            if (value > INT_MAX) {\n                return streak;\n            }\n            num = static_cast<int>(value);\n        }\n        return streak;\n    }\n};\n\n```\n```python []\nclass Solution:\n    def longestSquareStreak(self, nums: List[int]) -> int:\n        hs = set(nums)\n        max_streak = 0\n\n        def dp(num):\n            streak = 0\n            while num in hs:\n                streak += 1\n                value = num * num\n                if value > 2**31 - 1:  # Prevent overflow beyond int limit\n                    return streak\n                num = value\n            return streak\n\n        for num in nums:\n            max_streak = max(max_streak, dp(num))\n        \n        return max_streak if max_streak > 1 else -1\n```\nYOu can optimise this as well using memoization. Do give it a try.\n\n
['Array', 'Hash Table', 'Binary Search', 'Dynamic Programming', 'Sorting', 'Python', 'C++', 'Java']