Longest Square Streak in an Array — Problem & Solution
Longest Square Streak in an Array solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A medium problem.
Longest Square Streak in an Array is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon and Google interviews.
- Difficulty: Medium
- Topics: Arrays, Hash Table, Dynamic Programming, Binary Search
- Asked at: Amazon, Google
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
A subsequence of nums is a square streak when it has length at least 2 and, once sorted, every element except the first is the square of the element before it (for example 3, 9, 81).
Return the length of the longest square streak in nums, or -1 if there is none.
Example 1
Input: nums = [4,16,3,256,9,7]
Output: 3
Explanation: `[4,16,256]`: 16 = 4² and 256 = 16². `[3,9]` is a shorter streak.
Example 2
Input: nums = [2,3,5,6,7]
Output: -1
Example 3
Input: nums = [5,25,25,625]
Output: 3
Explanation: `[5,25,625]` — a value can be used only once in the streak, but duplicates do not hurt.
Constraints
2 <= nums.length <= 10^52 <= nums[i] <= 10^5
Hints for Longest Square Streak in an Array
Hint 1
Order in the array does not matter for a subsequence that gets sorted — only which values are present.
Hint 2
Put the values in a set and, from each value
v, followv, v², v⁴, …while the next value is present.Hint 3
Values are at most
10^5, so a chain is at most 5 long (2, 4, 16, 256, 65536); stop before squaring overflows.
How to solve Longest Square Streak in an Array
A streak is determined by its smallest value: the rest are forced (v², v⁴, …). So try every distinct value as the start and walk its chain through a hash set.
Approach
- Insert all values into a set.
- For each distinct value
v, setlen = 1,x = v, and whilex * xis in the set (andx * x <= 10^5), squarexand incrementlen. - Track the largest
lenthat is at least 2. - Return it, or
-1if no chain reached length 2.
Why it works
Sorting a square streak puts it in the order v, v², v⁴, …, so every streak is a prefix of the chain that starts at its smallest element, and the walk from that element finds the longest such prefix. Squares grow so fast that each walk takes at most four steps.
Complexity
- Time —
O(n) - Space —
O(n)
Pitfalls
v * voverflows 32-bit integers forv > 46340; checkv <= 316(or use 64-bit) before squaring.- A single element is not a streak — the answer is
-1, not 1. - Duplicated values do not lengthen a streak.
Reference solution
Python
from typing import List
def longestSquareStreak(nums: List[int]) -> int:
have = set(nums)
best = -1
for v in have:
length = 1
x = v
while x * x in have:
x = x * x
length += 1
if length >= 2 and length > best:
best = length
return bestJava
public static int longestSquareStreak(int[] nums) {
Set<Integer> have = new HashSet<>();
for (int v : nums) have.add(v);
int best = -1;
for (int v : have) {
int len = 1, x = v;
while (x <= 316 && have.contains(x * x)) {
x = x * x;
len++;
}
if (len >= 2 && len > best) best = len;
}
return best;
}C++
int longestSquareStreak(vector<int>& nums) {
unordered_set<int> have(nums.begin(), nums.end());
int best = -1;
for (int v : have) {
int len = 1, x = v;
while (x <= 316 && have.count(x * x)) {
x = x * x;
len++;
}
if (len >= 2 && len > best) best = len;
}
return best;
}JavaScript
var longestSquareStreak = function(nums) {
var have = new Set(nums);
var best = -1;
have.forEach(function(v) {
var len = 1, x = v;
while (x <= 316 && have.has(x * x)) {
x = x * x;
len++;
}
if (len >= 2 && len > best) best = len;
});
return best;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Hashing: Hash Maps and Hash Sets