You are given an integer array nums. A subsequence of nums is called a square streak if:
2, andReturn the length of the longest square streak in nums, or return -1 if there is no square streak.
A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.
Example 1:
Input: nums = [4,3,6,16,8,2] Output: 3 Explanation: Choose the subsequence [4,16,2]. After sorting it, it becomes [2,4,16]. - 4 = 2 * 2. - 16 = 4 * 4. Therefore, [4,16,2] is a square streak. It can be shown that every subsequence of length 4 is not a square streak.
Example 2:
Input: nums = [2,3,5,6,7] Output: -1 Explanation: There is no square streak in nums so return -1.
Constraints:
2 <= nums.length <= 1052 <= nums[i] <= 105Problem 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.
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.
The program begins by defining a helper function contains to determine if a squared value exists in the array. Then, for each element in the array, it calculates the squares sequentially. It keeps track of the maximum streak length, which is updated whenever a longer streak is found.
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.
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.
The C solution uses a dynamic programming array dp where each entry keeps track of the longest sequence ending with that element. It sorts the input array to facilitate streak calculations, checking possible backward links with previous elements.
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.
We first use a hash table to record all elements in the array. Then, we enumerate each element in the array as the first element of the subsequence, square this element continuously, and check whether the squared result is in the hash table. If it is, we use the squared result as the next element and continue checking until the squared result is not in the hash table. At this point, we check whether the length of the subsequence is greater than 1. If it is, we update the answer.
The time complexity is O(n times log log M), and the space complexity is O(n). Here, n is the length of the array nums, and M is the maximum value of the elements in the array nums.
Python
Java
C++
Go
TypeScript
JavaScript
Similar to Solution 1, we first use a hash table to record all elements in the array. Then, we design a function dfs(x), which represents the length of the square wave starting with x. The answer is max(dfs(x)), where x is an element in the array nums.
The calculation process of the function dfs(x) is as follows:
x is not in the hash table, return 0.1 + dfs(x^2).During the process, we can use memoization, i.e., use a hash table to record the value of the function dfs(x) to avoid redundant calculations.
The time complexity is O(n), and the space complexity is O(n). Here, n is the length of the array nums.
Python
Java
C++
Go
TypeScript
JavaScript
| Approach | Complexity |
|---|---|
| HashSet Based Approach | Time Complexity: O(n^1.5) in worst-case due to nested loops and nested search. |
| Dynamic Programming Approach | Time Complexity: O(n^2) due to nested loops used in the calculation of dp array. |
| Hash Table + Enumeration | — |
| Memoization Search | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet Based Approach | O(n log M) | O(n) | General case when the array is unsorted and fast membership checks are needed |
| Dynamic Programming with Sorting | O(n log n) | O(n) | When building chains incrementally after sorting or when avoiding repeated chain traversal |
Longest Square Streak in an Array | Detailed Approaches | Dry Run | Leetcode 2501 | codestorywithMIK • codestorywithMIK • 7,771 views views
Watch 9 more video solutions →Practice Longest Square Streak in an Array with our built-in code editor and test cases.
Practice on FleetCode