Problem of The Day: Longest Square Streak in an Array

Problem Statement

Intuition

The primary goal is to find the longest sequence where each element is a perfect square of the previous one. The intuition is to leverage the unique squares within the input list nums by using a set, allowing us to quickly check for the presence of squares in constant time.

Approach

1. Convert the list nums into a set, unique_nums, to allow for constant-time checks of whether the square of a number exists in nums.
2. Initialize res to -1, which will store the maximum sequence length found.
3. Loop through each number in nums, treating each as a potential start of a square-streak sequence.
   • For each number, initialize length to 1 and set curr to the current number.
   • While the square of curr exists in unique_nums, update curr to its square, incrementing length to track the streak’s length.
4. Update res with the maximum sequence length found that has at least two numbers (length >= 2).
5. Return res as the result.

Complexity

• Time Complexity: \(O(n \log \text{max}(nums))\), where (n) is the length of nums. For each number, we may need to check multiple squares up to the maximum possible value in nums.
• Space Complexity: \(O(n)\), required to store the unique elements in the set unique_nums.

Code

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        unique_nums = set(nums)
        res = -1
        for num in nums:
            length = 1
            curr = num
            while curr ** 2 in unique_nums:
                curr = curr ** 2
                length += 1
            if length >= 2:
                res = max(res, length)
        return res

Editorial

Approach 1: Binary Search

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        # Sort the array in ascending order
        nums.sort()

        # Set to keep track of numbers we've already processed
        processed_numbers = set()

        longest_streak = 0

        # Iterate through each number in the sorted array
        for current in nums:
            # Skip if we've already processed this number
            if current in processed_numbers:
                continue

            streak = current
            streak_length = 1

            # Continue the streak as long as we can find the square of the current number
            while streak * streak <= 10**5:
                if self._binary_search(nums, streak * streak):
                    streak *= streak
                    processed_numbers.add(streak)
                    streak_length += 1
                else:
                    break

            # Update the longest streak if necessary
            longest_streak = max(longest_streak, streak_length)

        # Return -1 if no valid streak found, otherwise return the longest streak
        return longest_streak if longest_streak >= 2 else -1

    # Binary search helper function to efficiently find a value in the sorted array
    def _binary_search(self, nums: List[int], target: int) -> bool:
        left, right = 0, len(nums) - 1

        while left <= right:
            mid = (left + right) // 2
            if nums[mid] == target:
                return True
            elif nums[mid] < target:
                left = mid + 1
            else:
                right = mid - 1

        return False

• time: O(nlogn)
• space: O(n)

Approach 2: Set

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        longest_streak = 0

        # Create a set to store all unique numbers from the input array
        unique_numbers = set(nums)

        # Iterate through each number in the input array
        for start_number in nums:
            current_streak = 0
            current = start_number

            # Continue the streak as long as we can find the next square in the set
            while current in unique_numbers:
                current_streak += 1

                # Break if the next square would be larger than 10^5 (problem constraint)
                if current * current > 10**5:
                    break

                current *= current

            # Update the longest streak if necessary
            longest_streak = max(longest_streak, current_streak)

        # Return -1 if no valid streak found, otherwise return the longest streak
        return longest_streak if longest_streak >= 2 else -1

• time: O(n)
• space: O(n)

Approach 3: Map

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        # Dictionary to store the length of square streak for each number
        streak_lengths = {}

        nums.sort()

        for number in nums:
            root = int(number**0.5)

            # Check if the number is a perfect square and its square root is in the dictionary
            if root * root == number and root in streak_lengths:
                # Extend the streak from its square root
                streak_lengths[number] = streak_lengths[root] + 1
            else:
                # Start a new streak
                streak_lengths[number] = 1

        # Find the maximum streak length
        longest_streak = max(streak_lengths.values(), default=0)

        # Return -1 if no valid streak found, otherwise return the longest streak
        return longest_streak if longest_streak > 1 else -1

• time: O(nlogn)
• space: O(n)