LeetCode 2501 - Longest Square Streak in an Array

Difficulty: 🟡 Medium
Topics: Array, Hash Table, Binary Search, Dynamic Programming, Sorting

Solution

Problem Understanding

The problem asks us to identify the longest square streak in an array of integers nums. A square streak is a subsequence of at least length 2 where, after sorting, every element is the square of the previous element. In other words, if the sorted subsequence is [x1, x2, ..., xk], then x2 = x1^2, x3 = x2^2, and so on.

The input nums is an unsorted array of integers, where each element ranges from 2 to 10^5, and the length of the array can be up to 10^5. The output should be a single integer, which is the length of the longest square streak or -1 if no valid streak exists.

Important edge cases to consider include:

Arrays where no square streak exists, e.g., [2,3,5].
Arrays where multiple streaks overlap, e.g., [2,4,16,256].
Arrays with repeated numbers, e.g., [2,2,4,16].
The minimum input size (nums.length = 2) and maximum input size (nums.length = 10^5).

The constraints suggest that brute-force exploration of all subsequences is infeasible due to combinatorial explosion, so an efficient approach is required.

Approaches

Brute Force Approach

A brute-force solution would involve generating all subsequences of nums, sorting each, and then checking if each element is the square of the previous. While this is correct, the number of subsequences grows exponentially with the length of the array, making it completely infeasible for nums.length up to 10^5.

Optimal Approach

The key insight for a more efficient solution is that the problem can be approached using a hash set and greedy chaining. Since the subsequence only requires sorting, we can ignore the original order during construction. We can store all numbers in a set for O(1) lookups, then for each number, repeatedly square it to see how long the chain can grow. We track the maximum length of all chains.

Additional efficiency is gained by processing numbers in ascending order. If a number x is already part of a longer chain starting from a smaller number, we can skip starting a chain from x.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n log n)	O(n)	Generates all subsequences, sorts, and checks
Optimal	O(n log n)	O(n)	Use set for fast lookup, chain growth by squaring numbers

Algorithm Walkthrough

Insert all numbers in nums into a hash set for O(1) lookups.
Sort nums in ascending order to start chains from the smallest numbers first.
Initialize a variable max_len to track the longest square streak found.
Iterate through each number num in the sorted array.
If num is not in the set (already visited as part of another chain), skip it.
Otherwise, initialize length = 1 and a variable current = num.
While current^2 exists in the set:
Increment length by 1.
Mark current as visited by removing it from the set.
Update current = current^2.
Update max_len with the maximum of its current value and length.
After processing all numbers, if max_len >= 2, return max_len, otherwise return -1.

Why it works: By starting from the smallest number in each potential streak and growing via squaring, we ensure that we find the longest possible subsequence. Using a set prevents revisiting numbers, avoiding redundant computations.

Python Solution

from typing import List

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        num_set = set(nums)
        nums.sort()
        max_len = -1

        for num in nums:
            if num not in num_set:
                continue

            length = 1
            current = num
            while current * current in num_set:
                current = current * current
                length += 1
                num_set.remove(current // current)  # previous current already used

            if length >= 2:
                max_len = max(max_len, length)

        return max_len

Implementation Walkthrough: The code first converts the list into a set for O(1) lookups and sorts it. For each number, it grows the chain by repeatedly squaring and removes elements from the set to prevent reuse. max_len is updated for streaks of length at least 2.

Go Solution

func longestSquareStreak(nums []int) int {
    numSet := make(map[int]bool)
    for _, num := range nums {
        numSet[num] = true
    }

    maxLen := -1

    // Sort nums
    sort.Ints(nums)

    for _, num := range nums {
        if !numSet[num] {
            continue
        }

        length := 1
        current := num
        for {
            square := current * current
            if _, exists := numSet[square]; !exists {
                break
            }
            current = square
            length++
            delete(numSet, current)
        }

        if length >= 2 && length > maxLen {
            maxLen = length
        }
    }

    return maxLen
}

Go Notes: The Go version uses a map for the set. Sorting is done with sort.Ints. Deletion from the map marks elements as visited, similar to removing from the Python set.

Worked Examples

Example 1: nums = [4,3,6,16,8,2]

Sorted: [2,3,4,6,8,16]
Start with 2: chain [2,4,16], length = 3 → max_len = 3
Start with 3: 3^2 = 9 not in set → skip
Start with 4: already removed → skip
Start with 6: 6^2 = 36 not in set → skip
Start with 8: 8^2 = 64 not in set → skip
Start with 16: already removed → skip
Return max_len = 3

Example 2: nums = [2,3,5,6,7]

Sorted: [2,3,5,6,7]
Chains: 2→4?, 3→9?, 5→25?, 6→36?, 7→49? → None in set
Return -1

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting takes O(n log n), and chain growth is O(n) since each number is visited at most once
Space	O(n)	Hash set stores all numbers

The algorithm efficiently handles large input sizes because each number is processed once in the chain growth, and sorting ensures we always start with the smallest candidate for a streak.

Test Cases

# Provided examples
assert Solution().longestSquareStreak([4,3,6,16,8,2]) == 3  # streak [2,4,16]
assert Solution().longestSquareStreak([2,3,5,6,7]) == -1  # no streak

# Edge cases
assert Solution().longestSquareStreak([2,4]) == 2  # minimum streak
assert Solution().longestSquareStreak([2,4,16,256]) == 4  # long chain
assert Solution().longestSquareStreak([3,9,81,2,4,16]) == 3  # multiple chains, choose longest
assert Solution().longestSquareStreak([2,2,4,16]) == 3  # repeated elements
assert Solution().longestSquareStreak([100000]) == -1  # single element, no streak

Test	Why
`[4,3,6,16,8,2]`	Valid streak of length 3
`[2,3,5,6,7]`	No valid streak
`[2,4]`	Minimal valid streak
`[2,4,16,256]`	Long chain
`[3,9,81,2,4,16]`	Multiple chains, pick longest
`[2,2,4,16]`	Handles duplicates correctly
`[100000]`	Single element, no streak

Edge Cases

Single chain vs multiple chains: When multiple square streaks exist, the algorithm must identify the longest. Sorting ensures smaller numbers are considered first, guaranteeing the longest chain is found.
Duplicate numbers: Duplicates can mislead chain counting if not handled correctly. By removing numbers from the set after use, duplicates do not inflate streak lengths incorrectly.
Large numbers: Squaring numbers can quickly exceed 10^5, so chains may terminate early. The implementation automatically stops when current^2 is not in the set, which