We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Longest Square Streak in an Array

Number: 2586

Difficulty: Medium

Paid? No

Companies: Meta, Amazon

Problem Description

Given an integer array nums, find the length of the longest square streak. A square streak is defined as a subsequence of at least two numbers that, after sorting the subsequence, forms a sequence where each element (except the first) is the square of the previous one. If no such streak exists, return -1.

Key Insights

  • Convert nums into a set for O(1) lookups.
  • For each number, build a chain by repeatedly squaring the current number if the square exists in the set.
  • To avoid redundant computation, only consider a number as a starting point if it is not the square of another number present in the set.
  • Since the maximum chain length is naturally limited by exponential growth, the algorithm runs efficiently even with large inputs.

Space and Time Complexity

Time Complexity: O(n * k) where n is the number of unique elements and k is the maximum chain length (which is small due to exponential growth).
Space Complexity: O(n) due to using a set for lookups.

Solution

We first create a set from nums to allow fast existence checks. Then for each unique number, we check if it can be a starting point by verifying that it is not the square of another number already present in the set. Starting from each valid candidate, we form a sequence by repeatedly checking and moving to its square. We keep track of the maximum length found. If the maximum is at least 2, we return it; otherwise, we return -1.

Code Solutions

# Python solution with line-by-line comments
import math
from typing import List

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        # Create a set for fast lookups.
        num_set = set(nums)
        max_length = 0
        
        # Iterate over each unique number in the set.
        for num in num_set:
            # Check if 'num' is a candidate starting point.
            # If 'num' is a perfect square and its square root exists in the set,
            # then it is part of a chain that has already been considered.
            root = int(math.isqrt(num))
            if root * root == num and root in num_set:
                continue  # Skip if num can be reached by squaring another number.
            
            # Start building the streak from the candidate number.
            curr = num
            length = 1
            
            # Continue extending the streak as long as the square exists in the set.
            while curr in num_set:
                next_val = curr * curr
                if next_val in num_set:
                    length += 1
                    curr = next_val
                else:
                    break
            
            # Update maximum streak length.
            max_length = max(max_length, length)
        
        # If the longest streak has at least 2 elements, return its length; otherwise, return -1.
        return max_length if max_length >= 2 else -1
← Back to All Questions