Longest Square Streak in an Array

Leetcode Problem:

• Longest Square Streak in an Array

Summary

• The problem is to find the length of the longest square streak in a given integer array
• A square streak is a subsequence where each element (except the first) is the square of the previous number
• The solution should return the length of the longest square streak or -1 if no square streak exists.

Approach

• The approach used in the solution is to first mark all numbers in the array as visited
• Then, for each number in the array, it checks if it is the square of any other number
• If it is, it counts the number of consecutive squares starting from that number
• The maximum count is updated if a longer square streak is found.

Complexity

• O(n * sqrt(m)) where n is the size of the array and m is the maximum number in the array

Explanation

• The solution uses a boolean array isNum to keep track of visited numbers
• It iterates over each number in the array and checks if it is the square of any other number
• If it is, it counts the number of consecutive squares starting from that number
• The maximum count is updated if a longer square streak is found
• The time complexity is O(n * sqrt(m)) because in the worst case, for each number in the array, it checks all numbers up to sqrt(m).

Solution Code:

class Solution {
public:
    bool isNum[100001] = {false};
    int longestSquareStreak(vector& nums) {
        for(int i = 0 ; i < nums.size(); i++){
            isNum[nums[i]] = true;
        }
        
        int ans = -1;
        for(int i = 0 ; i < 100001; i++){
            if (!isNum[i]) continue;
            long long j = i;
            int cnt = 0;
            while(j <= 100000 && isNum[j]){
                cnt++;
                j = j*j;
            }
            if(cnt >= 2)
                ans = max(ans, cnt);
        }
        return ans;
    }
};