Daily Problem 28th October | Using DP O(n^2) and HashMap O(n)
Using map\n- Time Complexity: O(n)\n- Space Complexity: O(n)\n# Code\ncpp []\nclass Solution {\npublic:\n    int longestSquareStreak(vector<int>& arr) {\n      
# Using map\n- **Time Complexity: O(n)**\n- **Space Complexity: O(n)**\n# Code\n```cpp []\nclass Solution {\npublic:\n    int longestSquareStreak(vector<int>& arr) {\n        int n = arr.size();\n        sort(arr.begin(), arr.end());\n        int ans = 0;\n        map<int, int> m;\n        for(auto x : arr) {\n            int sq = sqrt(x);\n            if(sq * sq == x) {\n                // now check if the value is present inside the map or not\n                if(m.count(sq)) {\n                    m[x] = m[sq] + 1;\n                } else {\n                    m[x] = 1;\n                }\n            } else m[x] = 1;\n        }\n\n        for(auto x : m) ans = max(x.second, ans);\n        return ans == 1 ? -1 : ans;\n    }\n};\n```\n\n# Using DP\n- **Time Complexity: O(n*n)**\n- **Space Complexity: O(n)**\n# Code\n```cpp []\nclass Solution {\npublic:\n    int longestSquareStreak(vector<int>& arr) {\n        int n = arr.size();\n        sort(arr.begin(), arr.end());\n        // 2 3 4 6 8 16\n        // 1 1 2 1 \n        int ans = 0;\n        vector<int> dp(n + 1,  1);\n        dp[0] = 0;\n        for(int i = 1;i <= n;i++) {\n            for(int j = 1;j < i;j++) {\n                if(arr[j - 1] * arr[j - 1] == arr[i - 1]) {\n                    dp[i] = max(1 + dp[j], dp[i]);\n                }\n            }\n            ans = max(ans, dp[i]);\n        }\n        // for(auto x: dp) cout << x << " ";\n        // cout << endl;\n        return ans == 1 ? -1 : ans;\n    }\n};\n```
['Hash Table', 'Dynamic Programming', 'Sorting', 'C++']