Sponsored
Sponsored
This approach leverages a HashSet for quick access to elements and checks subsequent squares in the sequence. We iterate over each number in the array, and for each number, keep finding its squares while incrementing the length of the streak. The longest streak is tracked and returned at the end.
Time Complexity: O(n^1.5) in worst-case due to nested loops and nested search.
Space Complexity: O(1) extra space for auxiliary storage as in-place checks are performed.
1def longest_square_streak(nums):
2 num_set = set(nums)
3 max_length = -1
4
5 for num in nums:
6 length = 1
7 current = num
8 while current * current in num_set:
9 length += 1
10 current *= current
11 if length > 1:
12 max_length = max(max_length, length)
13
14 return max_length
15
16nums = [4, 3, 6, 16, 8, 2]
17print(longest_square_streak(nums))In the Python implementation, the standard set collection provides a time-efficient way to check for elements. It processes each number and checks for its square's existence, calculating and comparing the streak length throughout.
This approach uses dynamic programming to store intermediate results regarding the longest square streak ending at each number. Sorting the array helps in ensuring that every subsequent square evaluated is in a larger-than relationship compared to previous elements, thus contributing to the streak length.
Time Complexity: O(n^2) due to nested loops used in the calculation of dp array.
Space Complexity: O(n) for managing the dp array.
1#include <vector>
#include <algorithm>
using namespace std;
int longestSquareStreakDP(vector<int>& nums) {
sort(nums.begin(), nums.end());
vector<int> dp(nums.size(), 1);
int maxLength = -1;
for (size_t i = 0; i < nums.size(); ++i) {
for (size_t j = 0; j < i; ++j) {
if (nums[i] == nums[j] * nums[j]) {
dp[i] = max(dp[i], dp[j] + 1);
}
}
if (dp[i] > 1) {
maxLength = max(maxLength, dp[i]);
}
}
return maxLength;
}
int main() {
vector<int> nums = {4, 3, 6, 16, 8, 2};
cout << longestSquareStreakDP(nums) << endl;
return 0;
}The C++ implementation uses sorting to facilitate processing, and constructs a dp vector dynamically storing maximum streak lengths ending at each position, hence optimizing overall results computation.