Beats 100% || 2 Extremely Easy DP Solution Detailed Explanation⭐🏆
Longest Square Streak\n\n## Problem Description\nGiven an array of integers nums, you are required to find the length of the longest subsequence where each elem
# Longest Square Streak\n\n## Problem Description\nGiven an array of integers `nums`, you are required to find the length of the longest subsequence where each element is a perfect square of its preceding element. If no such sequence with length greater than or equal to 2 exists, return `-1`.\n\n## Intuition\nThe initial intuition is to use a recursive approach with dynamic programming to keep track of the longest square streak that can be built with each element. By iterating through each element and using a hashmap to store square streak lengths, we can build the solution iteratively while minimizing the memory usage.\n\n## Approach\n1. **Sorting**: Sort the array to ensure that we only need to check for potential square sequences in one direction (from smaller to larger numbers).\n2. **HashMap for DP**: Use an `unordered_map` (hashmap) to store the length of the longest square streak ending at each element.\n3. **Square Check**: For each element, calculate its integer square root, and check if the square of that root equals the element. If it does, update the streak length by adding 1 to the value in the hashmap corresponding to that root.\n4. **Result**: Track the maximum streak length throughout, and if the maximum streak length is at least 2, return it. Otherwise, return `-1`.\n\n## Complexity\n- **Time complexity**: \\(O(n \\log n)\\) due to sorting the array, where \\(n\\) is the number of elements in `nums`.\n- **Space complexity**: \\(O(n)\\) for the hashmap that stores streak lengths for each element.\n\n## Code\n```cpp\nclass Solution {\npublic:\n    int solve(vector<int>& nums, int index, int prevIndex, vector<vector<int>>& dp) {\n        \n        if (index == nums.size()) {\n            return 0;\n        }\n\n        if (dp[index][prevIndex + 1] != -1) {\n            return dp[index][prevIndex + 1];\n        }\n\n        int skip = solve(nums, index + 1, prevIndex, dp);\n\n        int include = 0;\n        if (prevIndex == -1 || nums[index] == nums[prevIndex] * nums[prevIndex]) {\n            include = 1 + solve(nums, index + 1, index, dp);\n        }\n\n        return dp[index][prevIndex + 1] = max(include, skip);\n    }\n\n    // int longestSquareStreak(vector<int>& nums) {\n    //     sort(nums.begin(), nums.end());\n    //     // vector<vector<int>> dp(nums.size(), vector<int>(nums.size() + 1, -1));\n    //     // int maxLength = solve(nums, 0, -1, dp);\n    //     // return maxLength >= 2 ? maxLength : -1;\n\n    //     int n = nums.size();\n    //     vector<int> dp(n + 1, 0);  \n    //     int maxLength = 0;\n\n    //     for (int index = n - 1; index >= 0; index--) {\n    //         int currentMax = 0;\n    //         for (int nextIndex = index + 1; nextIndex < n; nextIndex++) {\n    //             if (static_cast<long long>(nums[index]) * nums[index] == nums[nextIndex]) {\n    //                 currentMax = max(currentMax, dp[nextIndex]);\n    //             }\n    //         }\n    //         dp[index] = 1 + currentMax;\n    //         maxLength = max(maxLength, dp[index]);\n    //     }\n\n    //     return maxLength >= 2 ? maxLength : -1;\n    // }\n\n    int longestSquareStreak(vector<int>& nums) {\n        \n        unordered_map<int, int> dp;\n        int res = 0;\n        sort(begin(nums), end(nums));\n\n        for(auto i : nums){\n            int root = sqrt(i);\n            if(root * root == i)\n                dp[i] = 1 + dp[root];\n            else \n                dp[i] = 1;\n            res = max(res, dp[i]);\n        }\n        return res < 2 ? -1 : res;\n    }\n};\n```
['Array', 'Hash Table', 'Binary Search', 'Dynamic Programming', 'Sorting', 'C++']