🔥C++ || Brute->Better->Best->Optimal || 5 Approaches || Easy Beginner Friendly || Beats 100%✅
Approach-1 ---> Brute Force\n# Intuition\nThe problem involves finding the longest streak of squares within an array. We aim to start from each element and chec
# Approach-1 ---> Brute Force\n# Intuition\nThe problem involves finding the longest streak of squares within an array. We aim to start from each element and check if the square of the current element exists in the array, extending the streak as long as each successive square can be found.\n\n# Approach\n##### Frequency Map Setup:\n Use an unordered map to store the occurrences of each element in the array. This helps to quickly check if a number\u2019s square exists in the array.\n#### Square Streak Calculation:\nFor each element in the array, set up a counter temp to track the current streak length and initialize num as the current element.\nUse a loop to calculate the square of num. If the square exists in the map, increment the streak counter, update num to this square, and continue. Otherwise, stop the streak.\n##### Track Maximum Streak: \nFor each element\'s square streak, keep track of the maximum streak encountered. If the longest streak found is 1, return -1; otherwise, return the longest streak.\n# Complexity\n##### Time Complexity: \nO(n log m), where n is the size of nums and m is the maximum element in nums. For each number, we calculate squares until the result exceeds the largest number in nums.\n##### Space Complexity:\n O(n), due to the space taken by the map to store each element\'s occurrence.\n\n# Code\n```cpp []\nclass Solution {\npublic:\n    int longestSquareStreak(vector<int>& nums) {\n        unordered_map<long long,int>mp;\n        int cnt=0;\n        for(auto& it:nums)\n        mp[it]++;\n\n        for(auto& it:nums)\n        {\n            int temp=1,num=it;\n            while(1)\n            {\n                long long mul=1LL*num*num;\n                if(mp.find(mul)==mp.end())\n                break;\n\n                temp++;\n                num=mul;\n            }\n            cnt=max(cnt,temp);\n        }\n        return cnt==1?-1:cnt;\n    }\n};\n```\n# Approach-2 ---> Binary Search\n# Intuition\nThe goal is to find the longest "square streak" in an array, where a square streak is a sequence starting from an element and repeatedly squaring it to get the next element in the sequence. Using binary search helps us efficiently search for the square of the current element in a sorted array.\n\n# Approach\n##### Sort the Array: \nSorting allows us to use binary search for finding the squares efficiently.\n##### Binary Search for Square Streak:\nFor each element, we initialize mul to its square, representing the next element in the square streak.\nUsing binary search, we look for mul in the remaining elements. If mul is found, increment the streak count, square mul again, and search for the new square from the current position to the end of the array.\nIf mul is not found, break the loop and continue to the next element.\nTrack Maximum Streak: For each element\u2019s streak, update the maximum streak length (cnt).\n##### Edge Case:\n If the longest streak is 1, return -1, as a valid streak requires at least one square transformation.\n# Complexity \n##### Time Complexity:\n O(n log n) for sorting and O(n log n) for iterating through each element and performing binary search, making the total time complexity O(n log n).\n##### Space Complexity: \nO(1) (excluding input/output) since no additional data structures are used beyond primitive variables.\n# Code\n```\nclass Solution {\npublic:\nint cnt,n;\nvoid solveUsingBS(int i,vector<int>& nums)\n{\n    int s=i,e=n-1,temp=1;\n    long long mul=1LL*nums[i]*nums[i];\n\n    while(s<=e)\n    {\n        int mid=s+(e-s)/2;\n        if(nums[mid]==mul)\n        {\n            temp++;\n            mul=1LL*nums[mid]*nums[mid];\n            e=n-1;\n        }\n        else if(nums[mid]>mul)\n        {\n            e=mid-1;\n        }\n        else\n        s=mid+1;\n    }\n    cnt=max(cnt,temp);\n}\n    int longestSquareStreak(vector<int>& nums) {\n        sort(nums.begin(),nums.end());\n\n        cnt=0,n=nums.size();\n\n        for(int i=0;i<n;i++)\n        {\n            solveUsingBS(i,nums);\n        }\n        return cnt==1?-1:cnt;\n    }\n};\n```\n# Approach-3 ---> Recursion\n# Intuition\nThe goal is to find the longest "square streak" in an array where each consecutive element in the streak is the square of the previous one. This recursive approach allows us to evaluate all possible square streaks by including or excluding each element based on whether it can extend a valid streak.\n\n# Approach\n##### Sorting the Array:\n\nSort nums to ensure we can check elements in increasing order, which allows us to explore the square streaks more systematically.\n##### Recursive Backtracking:\n\nDefine a recursive function solve(idx, prev_idx) where:\nidx is the current element index in nums.\nprev_idx is the index of the last included element in the streak.\n##### For each element at idx, determine if it can be included in the current streak by checking:\nEither there\u2019s no previous element in the streak (prev_idx == -1), or\nThe current element (nums[idx]) is the square of the previous element (nums[prev_idx]).\n##### Include or Exclude the Element:\nIf nums[idx] can extend the streak, call solve(idx + 1, idx) to include it.\nCall solve(idx + 1, prev_idx) to exclude nums[idx].\nTrack the maximum streak length from either including or excluding each element.\n##### Edge Case:\n\nIf the longest streak is 1, return -1, as a valid square streak must contain at least one square transformation.\n# Complexity Analysis\n##### Time Complexity:\n This recursive solution has O(2^n) complexity as it explores both inclusion and exclusion possibilities for each element, which makes it inefficient for large inputs.\n##### Space Complexity\n O(n) for the recursion stack.\n\n# Code\n```\nclass Solution {\npublic:\n    int n;\n    // 2,3,4,6,8,16\n    int solve(int idx,int prev_idx,vector<int>& nums)\n    {\n        if(idx>=n)\n        return 0;\n        int incl=0,excl=0;\n        \n        if( (prev_idx==-1 || (nums[idx]==(1LL*nums[prev_idx]*nums[prev_idx]))))\n        {\n            incl=1+solve(idx+1,idx,nums);\n        }\n        excl=solve(idx+1,prev_idx,nums);\n\n        return max(incl,excl);\n    }\n\n    int longestSquareStreak(vector<int>& nums) {\n        sort(nums.begin(),nums.end());\n        n=nums.size();\n        int ans=solve(0,-1,nums);\n        return ans==1?-1:ans;\n    }\n};\n```\n# Approach-4 ---> Memoization\n# Intuition\nTo find the longest "square streak" in an array where each consecutive element is the square of the previous one, we use a recursive approach with memoization. Memoization helps store previously computed results to avoid redundant calculations and optimize performance, especially when overlapping subproblems are involved.\n\n# Approach\n##### Sorting the Array:\n\nFirst, we sort nums to process elements in increasing order, enabling us to check if each element can extend a square streak.\nRecursive Function with Memoization:\n\n##### Define solveMemo(idx, prev_idx):\nidx is the current element index.\nprev_idx is the index of the last element in the current streak. A prev_idx of -1 indicates the start of a new streak.\nFor each idx, check if nums[idx] can extend the streak starting from nums[prev_idx]:\nInclude nums[idx] if prev_idx is -1 (new streak) or if it equals nums[prev_idx] squared.\nUse memoization with dp[idx][prev_idx+1] to store the result, where dp[idx][prev_idx+1] saves the longest streak length for the given indices.\n##### Edge Case:\n\nIf the longest streak is 1, return -1 as it doesn\'t qualify as a square streak without a transformation.\n# Complexity Analysis\nTime Complexity: O(n\xB2), where n is the size of nums. Each state (idx, prev_idx) is computed once and stored in dp.\nSpace Complexity: O(n\xB2) for the dp array, as it stores results for each possible combination of idx and prev_idx. Additionally, O(n) space is used for the recursion stack.\n# Code\n```\nclass Solution {\npublic:\n    int n;\n    // int solve(int idx,int prev_idx,vector<int>& nums)\n    // {\n    //     if(idx>=n)\n    //     return 0;\n    //     int incl=0,excl=0;\n        \n    //     if( (prev_idx==-1 || (nums[idx]==(1LL*nums[prev_idx]*nums[prev_idx]))))\n    //     {\n    //         incl=1+solve(idx+1,idx,nums);\n    //     }\n    //     excl=solve(idx+1,prev_idx,nums);\n    //     return max(incl,excl);\n    // }\n    int solveMemo(int idx,int prev_idx,vector<int>& nums,vector<vector<int>>& dp)\n    {\n        if(idx>=n)\n        return 0;\n\n        if(dp[idx][prev_idx+1]!=-1)\n        return dp[idx][prev_idx+1];\n        \n        int incl=0,excl=0;\n        \n        if( (prev_idx==-1 || (nums[idx]==(1LL*nums[prev_idx]*nums[prev_idx]))))\n        {\n            incl=1+solveMemo(idx+1,idx,nums,dp);\n        }\n        excl=solveMemo(idx+1,prev_idx,nums,dp);\n        return dp[idx][prev_idx+1]= max(incl,excl);\n    }\n\n    int longestSquareStreak(vector<int>& nums) {\n        sort(nums.begin(),nums.end());\n        n=nums.size();\n        // int ans=solve(0,-1,nums);\n        vector<vector<int>>dp(n+1,vector<int>(n+2,-1));\n        int ans=solveMemo(0,-1,nums,dp);\n        return ans==1?-1:ans;\n    }\n};\n```\n# Approach-5 ---> Tabulation Space Optimized\n# Intuition\nTo optimize the previous memoized approach, we can apply tabulation (bottom-up dynamic programming) with space optimization. This approach avoids the recursive overhead by building the solution iteratively from smaller subproblems and reduces space complexity by keeping only two arrays for the current and next row.\n\n# Approach\n##### Sorting the Array:\n\nSorting nums helps in maintaining a sequence where we can check each element\u2019s "square streak" efficiently.\n##### Iterative DP with Space Optimization:\n\nWe create two 1D arrays, next_row and curr, to store results for each possible combination of idx and prev_idx.\nStarting from the last element in nums, we iterate backwards to fill our DP table from the bottom up.\n##### For each element nums[idx], we check two cases:\nInclude nums[idx] if it\u2019s the start of a new streak or a square of the previous number nums[prev_idx].\nExclude nums[idx], where we take the maximum streak length found so far.\nAt the end of each loop for idx, update next_row with curr to proceed to the next set of subproblems.\n##### Edge Case:\n\nIf the longest streak found is 1, we return -1 as there are no transformations.\n# Complexity Analysis\nTime Complexity: O(n\xB2), due to the nested loop where each element and each possible previous index is iterated.\nSpace Complexity: O(n), using two 1D arrays of size n + 2 for next_row and curr.\n# Code\n```\nclass Solution {\npublic:\n    int n;\n    // int solve(int idx,int prev_idx,vector<int>& nums)\n    // {\n    //     if(idx>=n)\n    //     return 0;\n    //     int incl=0,excl=0;\n        \n    //     if( (prev_idx==-1 || (nums[idx]==(1LL*nums[prev_idx]*nums[prev_idx]))))\n    //     {\n    //         incl=1+solve(idx+1,idx,nums);\n    //     }\n    //     excl=solve(idx+1,prev_idx,nums);\n    //     return max(incl,excl);\n    // }\n    // int solveMemo(int idx,int prev_idx,vector<int>& nums,vector<vector<int>>& dp)\n    // {\n    //     if(idx>=n)\n    //     return 0;\n\n    //     if(dp[idx][prev_idx+1]!=-1)\n    //     return dp[idx][prev_idx+1];\n        \n    //     int incl=0,excl=0;\n        \n    //     if( (prev_idx==-1 || (nums[idx]==(1LL*nums[prev_idx]*nums[prev_idx]))))\n    //     {\n    //         incl=1+solveMemo(idx+1,idx,nums,dp);\n    //     }\n    //     excl=solveMemo(idx+1,prev_idx,nums,dp);\n    //     return dp[idx][prev_idx+1]= max(incl,excl);\n    // }\n\n    int solveTab(vector<int>& nums)\n{\n    int n = nums.size();\n    vector<int> next_row(n + 2, 0), curr(n + 2, 0);\n\n    for (int idx = n - 1; idx >= 0; idx--)\n    {\n        for (int prev_idx = idx - 1; prev_idx >= -1; prev_idx--)\n        {\n            int incl = 0, excl = 0;\n\n            if (prev_idx == -1 || nums[idx] == 1LL * nums[prev_idx] * nums[prev_idx])\n            {\n                incl = 1 + next_row[idx + 1];\n            }\n            excl = next_row[prev_idx + 1];\n\n            curr[prev_idx + 1] = max(incl, excl);\n        }\n        next_row = curr; \n    }\n    return next_row[0];\n}\n\n\n    int longestSquareStreak(vector<int>& nums) {\n        sort(nums.begin(),nums.end());\n        n=nums.size();\n        // int ans=solve(0,-1,nums);\n        // vector<vector<int>>dp(n+1,vector<int>(n+2,-1));\n        // int ans=solveMemo(0,-1,nums,dp);\n        int ans=solveTab(nums);\n        return ans==1?-1:ans;\n    }\n};\n```\n![63386845-cd1f-4d9e-a943-dac485d70f1c_1718868880.9913037.gif](https://assets.leetcode.com/users/images/f33cedc2-e2bf-40c3-9adc-a116b9bee3df_1730106796.214102.gif)\n\n
['Array', 'Hash Table', 'Binary Search', 'Dynamic Programming', 'Recursion', 'Memoization', 'Sorting', 'C++']