Longest Square Streak in an Array

Longest Square Streak in an Array

What is this problem about?

The Longest Square Streak in an Array interview question provides an array of integers. A "square streak" is a subsequence where each number (after the first) is the exact square of the previous number. For example, [2, 4, 16, 256] is a valid square streak. Your goal is to find the length of the longest possible square streak in the array. If no streak of at least length 2 exists, return -1.

Why is this asked in interviews?

This is a great, straightforward problem to test Hash Table lookups and sorting logic. Interviewers use it to see if candidates can identify chain-building sequences efficiently. It quickly separates candidates who write nested $O(N^2)$ loops from those who understand that pre-storing elements in a set allows for rapid $O(1)$ verification of future states.

Algorithmic pattern used

This problem is best solved using a Hash Set and Sorting. First, you sort the unique elements of the array in ascending order and store them in a Hash Set for instant lookups. Then, you iterate through the sorted numbers. For each number, you repeatedly square it and check if the squared value exists in the Hash Set, counting how many steps the chain survives.

Example explanation

Let nums = [4, 3, 6, 16, 8, 2].

1. Sort and convert to a Set: {2, 3, 4, 6, 8, 16}.
2. Iterate through the set:
   • Start with 2. Square is 4. 4 is in set! Streak = 2.
   • Square of 4 is 16. 16 is in set! Streak = 3.
   • Square of 16 is 256. Not in set. Sequence ends. Max streak is 3.
   • Start with 3. Square is 9. Not in set.
   • Start with 4. Square is 16. Streak = 2. (Already counted in 2's chain, but checking again is fine). The longest streak is [2, 4, 16] with a length of 3.

Common mistakes candidates make

A common error is not checking for integer overflow. Squaring large numbers repeatedly can quickly exceed standard 32-bit integer limits, throwing an exception or returning garbage data in languages like Java or C++. You must cast the value to a long before squaring it. Another mistake is forgetting to return -1 if the max streak found is less than 2.

Interview preparation tip

When solving the Longest Square Streak coding problem, you can actually optimize it further using Dynamic Programming on the sorted array. If you map dp[num] = dp[sqrt(num)] + 1 (if the square root is a perfect integer and exists in the array), you can build the chains in a single pass without while loops, demonstrating a deeper level of algorithmic thinking to your interviewer.