Longest Square Streak in an Array - Video Solutions

Problem Overview: You are given an integer array and need the length of the longest sequence where every next number equals the square of the previous one. For example, a chain like 2 → 4 → 16 → 256. The sequence must exist entirely inside the array, and if the longest chain has length less than 2, the answer is -1.

Approach 1: HashSet Based Approach (O(n log M) time, O(n) space)

Store all numbers in a HashSet for O(1) membership checks. For each number, repeatedly square the current value and check if the squared value exists in the set. Continue extending the chain until the square is missing. Track the maximum length seen across all starting values. The key insight is constant-time lookup using a hash structure, which makes chain expansion efficient. This approach works well for unsorted arrays and is a natural application of a hash table with basic iteration over an array.

Approach 2: Dynamic Programming with Sorting (O(n log n) time, O(n) space)

Sort the array first so smaller values are processed before their squares. Maintain a map dp[num] representing the longest square chain ending at num. For each value, compute its integer square root. If the root exists in the map and root * root == num, extend the chain with dp[num] = dp[root] + 1. Otherwise start a new chain with length 1. Sorting ensures the potential predecessor appears earlier, allowing a clean bottom‑up dynamic programming transition. This approach avoids repeatedly exploring the same chains and keeps updates predictable.

Recommended for interviews: The HashSet approach is typically the fastest to implement and demonstrates strong understanding of constant-time lookups and sequence expansion. Interviewers often expect this idea because it directly models the square relationship. The DP + sorting approach shows deeper algorithmic thinking by building results incrementally and avoiding redundant chain exploration. Knowing both approaches signals strong problem-solving depth.