Longest Square Streak in an Array

Medium

Asked by:

21 views

Topics:

ArraysGreedy Algorithms

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.

A subsequence is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.

Example 1:

Input: nums = [4,3,6,16,8,2]
Output: 3
Explanation: Choose the subsequence [4,16,2]. After sorting it, it becomes [2,4,16].
- 4 = 2 * 2.
- 16 = 4 * 4.
Therefore, [4,16,2] is a square streak.
It can be shown that every subsequence of length 4 is not a square streak.

Example 2:

Input: nums = [2,3,5,6,7]
Output: -1
Explanation: There is no square streak in nums so return -1.

Constraints:

2 <= nums.length <= 10⁵
2 <= nums[i] <= 10⁵

Try coding it in LeetCode

Solution

Clarifying Questions

When you get asked this question in a real-life environment, it will often be ambiguous (especially at FAANG). Make sure to ask these questions in that case:

What is the range of values for the integers in the input array? Can they be negative, zero, or very large?
Are there any constraints on the size (length) of the input array?
If no square streak exists (even of length 2), what should the function return? Is there a specific value I should return (e.g., -1, 0, null)?
Are duplicate numbers allowed in the input array, and if so, how should they be handled when determining the longest square streak?
If multiple square streaks of the same maximum length exist, should I return any one of them, or is there a specific one I should return (e.g., the one that starts with the smallest number)?

Brute Force Solution

Approach

The brute force approach finds the longest square streak by checking every possible sequence of numbers in the given list. For each number, we see if its square is also in the list, then the square of that number, and so on. We keep track of the longest sequence we find in this manner.

Here's how the algorithm would work step-by-step:

Pick the first number from the list.
Check if its square is also in the list.
If the square exists, check if the square of the square is in the list, and continue this squaring and checking process as long as the squared value exists in the list.
Keep track of how many numbers were in this sequence.
Repeat the process, starting with the second number in the list, then the third, and so on until every number in the list has been considered as the starting point for a possible sequence.
Compare the lengths of all the sequences found. The longest sequence is the answer.

Code Implementation

def longest_square_streak_brute_force(numbers):
    longest_streak = -1

    for starting_number in numbers:
        current_number = starting_number
        current_streak_length = 1
        
        # Use a set for faster lookups
        numbers_set = set(numbers)

        # Check for the existence of squares.
        while (current_number * current_number) in numbers_set:

            current_number = current_number * current_number
            current_streak_length += 1

        # Need to update the longest streak
        longest_streak = max(longest_streak, current_streak_length)

    if longest_streak < 2:
        return -1
    else:
        return longest_streak

Big(O) Analysis

Time Complexity

O(n*sqrt(M)) – The outer loop iterates through each of the n numbers in the input array. For each number, the inner loop squares the current number and checks if the square exists in the array. This continues until the squared value is no longer in the array or exceeds the maximum possible value M in the array. Because the numbers are repeatedly squared, the inner loop will execute at most approximately sqrt(M) times where M is the largest number in the input array. Therefore, the overall time complexity is approximately O(n * sqrt(M)).

Space Complexity

O(1) – The brute force approach, as described, does not use any auxiliary data structures like lists, sets, or maps to store intermediate results or track visited numbers. It iterates through the input array and performs calculations on individual numbers. Therefore, the space used is constant, independent of the input array's size N.

Optimal Solution

Approach

The goal is to find the longest chain of numbers where each number is the square of the previous one. We can do this efficiently by checking if the square root of a number exists in our set of numbers.

Here's how the algorithm would work step-by-step:

First, organize the numbers so we can quickly check if a number is present.
Then, for each number, see if it can be the start of a streak. We do this by checking if its square root is in the set of numbers.
If a number's square root exists, it can't start a streak, so we ignore it.
For each number that *can* start a streak, build the streak by repeatedly squaring the number and checking if the result exists in the set.
Keep track of the longest streak found so far and update it as you build new streaks.
Finally, return the length of the longest streak.

Code Implementation

def longest_square_streak(numbers):
    number_set = set(numbers)
    longest_streak_length = 0

    for number in numbers:
        # If the square root exists, it's part of a longer chain and cant start
        if (number ** 0.5).is_integer() and int(number ** 0.5) in number_set:
            continue

        current_streak_length = 1
        current_number = number

        # Build the streak by squaring the number
        while current_number * current_number in number_set:
            current_number *= current_number
            current_streak_length += 1

        # Update the longest streak if needed
        longest_streak_length = max(longest_streak_length, current_streak_length)

    # If the longest streak is less than 2, no streak exists.
    if longest_streak_length < 2:
        return -1

    return longest_streak_length

Big(O) Analysis

Time Complexity

O(n log n) – Converting the input array of size n into a set allows for O(1) average-case lookup. The code iterates through each of the n elements of the input array. Inside the loop, it repeatedly checks for the existence of squared numbers in the set. Each check within the while loop takes O(1) time due to the set lookup. The maximum number of iterations within the while loop is bound by the logarithm of the largest possible number, since we are repeatedly squaring the current number. Therefore, the overall time complexity is O(n log n).

Space Complexity

O(N) – The solution utilizes a set to store the input numbers for quick lookups. This set's size grows linearly with the number of elements in the input array. Therefore, the auxiliary space required is proportional to N, where N is the number of elements in the input array. Other variables used, like the current streak length and longest streak length, use constant space and do not depend on N, so the set dominates space complexity.

Edge Cases

Case	How to Handle
Empty or null input array	Return 0 immediately as there's no streak possible.
Array with only one element	Return 0 because a streak requires at least two numbers where one is the square of the other.
Array contains negative numbers	Ignore negative numbers as they cannot be part of a square streak (squares are non-negative).
Array contains zero	Zero can only be part of a streak if it is paired with itself (0 * 0 = 0), which should be handled correctly, but can be an edge case to consider if zero is present only once
Array contains duplicate positive numbers	The longest streak should only consider unique numbers once so the solution must handle duplicates appropriately
Integer overflow when squaring large numbers	Use long data type or check for potential overflow before performing the square operation.
Array contains extreme boundary values (e.g., maximum integer)	Handle largest integer carefully when performing square or other mathematical operations to prevent overflow.
No valid square streak exists in the array	Return 0 when no valid streak is found during the iteration.

Empty or null input array

How to Handle:

Return 0 immediately as there's no streak possible.

Array with only one element

How to Handle:

Return 0 because a streak requires at least two numbers where one is the square of the other.

Array contains negative numbers

How to Handle:

Ignore negative numbers as they cannot be part of a square streak (squares are non-negative).

Array contains zero

How to Handle:

Zero can only be part of a streak if it is paired with itself (0 * 0 = 0), which should be handled correctly, but can be an edge case to consider if zero is present only once

Array contains duplicate positive numbers

How to Handle:

The longest streak should only consider unique numbers once so the solution must handle duplicates appropriately

Integer overflow when squaring large numbers

How to Handle:

Use long data type or check for potential overflow before performing the square operation.

Array contains extreme boundary values (e.g., maximum integer)

How to Handle:

Handle largest integer carefully when performing square or other mathematical operations to prevent overflow.

No valid square streak exists in the array

How to Handle:

Return 0 when no valid streak is found during the iteration.