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

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Longest Square Streak in an Array

Difficulty: Medium

Problem Description

You are given an integer array nums. A subsequence of nums is called a square streak if:

  • The length of the subsequence is at least 2, and
  • After sorting the subsequence, each element (except the first element) is the square of the previous number.

Return the length of the longest square streak in nums, or return -1 if there is no square streak.

Key Insights

  • A square streak can only be formed by numbers that can be represented as powers of 2, i.e., if x is in the subsequence, x^2 must also be present.
  • The subsequence must be sorted, which implies that we need to check for the square relationship in an ordered manner.
  • Using a set can help in checking the existence of squares efficiently.

Space and Time Complexity

Time Complexity: O(n log n), where n is the number of elements in nums (due to sorting). Space Complexity: O(n), for storing the set of numbers.

Solution

To solve this problem, we can follow these steps:

  1. Store the elements of nums in a set for O(1) average-time complexity lookups.
  2. Sort the unique elements of nums.
  3. Iterate through the sorted list, and for each number, check if its square exists in the set.
  4. Track the length of streaks formed by consecutive numbers that can create a square streak.
  5. Return the maximum length found, or -1 if no streaks of length 2 or more are found.

Code Solutions

def longestSquareStreak(nums):
    nums_set = set(nums)
    sorted_nums = sorted(nums_set)
    max_streak = 0

    for num in sorted_nums:
        current_streak = 1
        current_num = num

        while current_num * current_num in nums_set:
            current_num = current_num * current_num
            current_streak += 1
        
        if current_streak > 1:
            max_streak = max(max_streak, current_streak)

    return max_streak if max_streak >= 2 else -1
← Back to All Questions