Longest Square Streak in an Array

Medium
1167.

Longest Square Streak in an Array

Longest Square Streak in an Array is a medium coding problem on arrays, hash table and dynamic programming, asked in Amazon and Google interviews.

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^5
  • 2 <= nums[i] <= 10^5
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} nums
 * @return {number}
 */
var longestSquareStreak = function(nums) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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.

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^5
  • 2 <= nums[i] <= 10^5

Hints for Longest Square Streak in an Array

  1. Hint 1

    Order in the array does not matter for a subsequence that gets sorted — only which values are present.

  2. Hint 2

    Put the values in a set and, from each value v, follow v, v², v⁴, … while the next value is present.

  3. 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

  1. Insert all values into a set.
  2. For each distinct value v, set len = 1, x = v, and while x * x is in the set (and x * x <= 10^5), square x and increment len.
  3. Track the largest len that is at least 2.
  4. Return it, or -1 if 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 * v overflows 32-bit integers for v > 46340; check v <= 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 best

Java

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