Problem Description

You need to find the longest "square streak" in an integer array nums.

A square streak is a subsequence that meets two conditions:

• It contains at least 2 elements
• When sorted, each element (except the first) equals the square of the previous element

For example, [2, 4, 16] is a valid square streak because 4 = 2² and 16 = 4².

The task is to return the length of the longest square streak found in nums. If no valid square streak exists, return -1.

Key Points:

• A subsequence maintains the relative order of elements from the original array but doesn't need to be contiguous
• The subsequence must form a chain where each number is the square of the previous one
• The minimum valid length is 2

Solution Explanation:

The solution uses a hash table approach. First, all elements from nums are stored in a set s for O(1) lookup. Then, for each number x in the array, it attempts to build a square streak starting from that number:

1. Start with current number x and counter t = 0
2. While x exists in the set:
   • Square the current number: x = x * x
   • Increment the counter t
3. If t > 1 (meaning we found at least 2 elements in the streak), update the maximum answer

The algorithm tracks the longest streak found across all starting points and returns it, or -1 if no valid streak exists.

Intuition

The key insight is that we need to find chains where each element is the square of the previous one. Since squaring grows numbers very quickly (e.g., 2 → 4 → 16 → 256 → 65536), these chains tend to be relatively short.

We can think of this problem as finding the longest path in a directed graph where there's an edge from a to b if b = a² and both exist in our array. Instead of building the entire graph, we can explore paths on-the-fly.

The natural approach is to try each number as a potential starting point of a streak. For each starting number, we keep squaring it and checking if the result exists in our array. This continues until we reach a number whose square isn't in the array.

Why use a hash set? Because we need to repeatedly check "does this squared value exist in the array?" A hash set gives us O(1) lookups, making the checking process efficient.

An important observation: we don't need to worry about finding the "optimal" starting point first. We can simply try every number as a potential start and keep track of the maximum streak length found. Even if we start from a middle element of a potential streak, we'll eventually try the actual first element and find the full length.

The squaring operation naturally ensures the sequence is increasing, so we don't need to explicitly sort or maintain order - we just follow the chain of squares until it breaks.

Learn more about Binary Search, Dynamic Programming and Sorting patterns.

Solution Approach

The implementation uses a hash table (set) combined with enumeration to find the longest square streak.

Step 1: Create a Hash Set

s = set(nums)

We convert the array into a set for O(1) lookup time. This allows us to quickly check if a squared value exists in the original array.

Step 2: Initialize the Answer

ans = -1

Start with -1 to handle the case where no valid square streak exists.

Step 3: Enumerate Each Starting Point

for x in nums:

Try each element in the array as a potential starting point for a square streak.

Step 4: Build the Square Streak For each starting element x:

t = 0
while x in s:
    x *= x
    t += 1

• Initialize a counter t to track the streak length
• Keep squaring x (using x *= x which is equivalent to x = x * x)
• Check if the squared value exists in the set
• Increment the counter for each valid element found
• Continue until we reach a value whose square isn't in the set

Step 5: Update the Maximum

if t > 1:
    ans = max(ans, t)

Only update the answer if we found a streak of length at least 2 (since a valid square streak requires minimum 2 elements).

Time Complexity: O(n × log(log(M))) where n is the array length and M is the maximum value. The log(log(M)) factor comes from the fact that squaring grows exponentially fast, so we can only square a number a very limited number of times before it exceeds any reasonable bound.

Space Complexity: O(n) for storing the hash set.

The algorithm efficiently finds all possible square streaks by trying each element as a starting point and following the chain of squares as far as possible.

Example Walkthrough

Let's walk through the algorithm with nums = [4, 3, 6, 16, 8, 2].

Step 1: Create hash set

s = {4, 3, 6, 16, 8, 2}

Step 2: Try each element as a starting point

Starting with x = 4:

• t = 0
• Is 4 in set? Yes → x = 4 * 4 = 16, t = 1
• Is 16 in set? Yes → x = 16 * 16 = 256, t = 2
• Is 256 in set? No → stop
• t = 2 > 1, so ans = 2

Starting with x = 3:

• t = 0
• Is 3 in set? Yes → x = 3 * 3 = 9, t = 1
• Is 9 in set? No → stop
• t = 1 is not > 1, so no update

Starting with x = 6:

• t = 0
• Is 6 in set? Yes → x = 6 * 6 = 36, t = 1
• Is 36 in set? No → stop
• t = 1 is not > 1, so no update

Starting with x = 16:

• t = 0
• Is 16 in set? Yes → x = 16 * 16 = 256, t = 1
• Is 256 in set? No → stop
• t = 1 is not > 1, so no update

Starting with x = 8:

• t = 0
• Is 8 in set? Yes → x = 8 * 8 = 64, t = 1
• Is 64 in set? No → stop
• t = 1 is not > 1, so no update

Starting with x = 2:

• t = 0
• Is 2 in set? Yes → x = 2 * 2 = 4, t = 1
• Is 4 in set? Yes → x = 4 * 4 = 16, t = 2
• Is 16 in set? Yes → x = 16 * 16 = 256, t = 3
• Is 256 in set? No → stop
• t = 3 > 1, so ans = max(2, 3) = 3

Result: The longest square streak is [2, 4, 16] with length 3.

Notice how starting from different points in the same streak (like starting from 4 vs starting from 2) gives different lengths. By trying all starting points, we ensure we find the maximum possible length.

Solution Implementation

Time and Space Complexity

Time Complexity: O(n × log log M)

The algorithm iterates through each element in nums (contributing O(n)). For each element x, it repeatedly squares the value and checks if it exists in the set. The key insight is determining how many times we can square a number before it exceeds the maximum value M.

Starting from a value x, after k squaring operations, we get x^(2^k). The loop continues while x^(2^k) ≤ M. Taking logarithms: 2^k × log(x) ≤ log(M), which gives us k ≤ log(log(M)/log(x)). In the worst case when x = 2 (the smallest base that can form a streak), we get approximately k ≤ log log M iterations.

Since each element can trigger at most O(log log M) iterations, and we process n elements, the total time complexity is O(n × log log M).

Space Complexity: O(n)

The algorithm uses a set s to store all elements from the input array nums, which requires O(n) space. The only other variables used are ans, t, and x, which require constant space. Therefore, the overall space complexity is O(n).

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Integer Overflow When Squaring Large Numbers

The most critical pitfall in this solution is that squaring numbers can quickly lead to integer overflow. When we compute current_value = current_value * current_value, the result can exceed the maximum integer limit, especially after just a few iterations.

Example of the Problem:

• Starting with 46340: 46340² = 2,147,395,600 (still within 32-bit int range)
• Next iteration: 2,147,395,600² ≈ 4.6 × 10^18 (overflow!)

Solution: Add an overflow check before squaring:

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        num_set = set(nums)
        max_streak_length = -1
      
        # Define a reasonable upper bound to prevent overflow
        MAX_LIMIT = 10**5  # Adjust based on problem constraints
      
        for num in nums:
            current_streak_length = 0
            current_value = num
          
            while current_value in num_set:
                # Check if squaring would exceed our limit
                if current_value > MAX_LIMIT:
                    break
                  
                current_value = current_value * current_value
                current_streak_length += 1
          
            if current_streak_length > 1:
                max_streak_length = max(max_streak_length, current_streak_length)
      
        return max_streak_length

2. Redundant Computation for Elements in the Same Streak

The current solution may redundantly compute streaks for numbers that are part of another number's streak. For instance, if we have [2, 4, 16], we compute the streak starting from 2 (finding 2→4→16), then again from 4 (finding 4→16), and again from 16.

Solution: Track visited numbers or only start streaks from "root" elements (numbers that aren't squares of any other number in the set):

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        num_set = set(nums)
        max_streak_length = -1
        visited = set()
      
        for num in nums:
            # Skip if this number was already part of another streak
            if num in visited:
                continue
              
            current_streak_length = 0
            current_value = num
            streak_elements = []
          
            while current_value in num_set and current_value <= 10**5:
                streak_elements.append(current_value)
                current_value = current_value * current_value
                current_streak_length += 1
          
            # Mark all elements in this streak as visited
            visited.update(streak_elements)
          
            if current_streak_length > 1:
                max_streak_length = max(max_streak_length, current_streak_length)
      
        return max_streak_length

3. Not Handling Edge Cases with Duplicates

If the input contains duplicate numbers, the set conversion removes them, which is correct for this problem. However, developers might mistakenly think they need to handle duplicates specially.

Key Understanding: Duplicates don't affect the solution because:

• A square streak is about unique values forming a sequence
• [2, 2, 4, 16] has the same longest streak as [2, 4, 16]

The set conversion naturally handles this correctly, so no additional logic is needed.