Longest Square Streak in an Array

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.

For example, if nums = [4,3,6,16,8,2], the answer is 3 because the subsequence [2,4,16] can be sorted to [2,4,16] where 4 = 22 and 16 = 44. As another example, if nums = [2,3,5,6,7], the answer is -1 because there is no square streak.

## Naive Solution

The most straightforward approach is to iterate through all possible subsequences of the input array `nums`, check if each subsequence is a square streak, and keep track of the longest square streak found so far. This can be done using recursion or iteration with bit manipulation to generate all possible subsequences.

```python
def longest_square_streak_naive(nums):
    n = len(nums)
    max_len = -1

    for i in range(1 << n):  # Iterate through all possible subsequences
        subsequence = []
        for j in range(n):
            if (i >> j) & 1:
                subsequence.append(nums[j])

        if len(subsequence) >= 2:
            subsequence.sort()
            is_square_streak = True
            for k in range(1, len(subsequence)):
                if subsequence[k] != subsequence[k-1] * subsequence[k-1]:
                    is_square_streak = False
                    break

            if is_square_streak:
                max_len = max(max_len, len(subsequence))

    return max_len

Optimal Solution

To improve efficiency, we can use a set to store all the numbers in the input array. Then, starting with each number, we can check if its square is also in the set. If it is, we extend the square streak. We repeat this process until no more squares are found in the set. We keep track of the longest streak found so far.

def longest_square_streak(nums):
    num_set = set(nums)
    max_len = -1

    for num in nums:
        if num in num_set:
            current_len = 1
            current_num = num
            while current_num * current_num in num_set:
                current_len += 1
                num_set.remove(current_num)
                current_num *= current_num
            
            if current_len >= 2:
                max_len = max(max_len, current_len)

    return max_len

Big(O) Run-time Analysis

• Naive Solution: Generating all subsequences takes O(2^n) time, where n is the number of elements in nums. For each subsequence, we sort it in O(k log k) time, where k is the length of the subsequence. Checking if it's a square streak takes O(k) time. Therefore, the overall time complexity is O(2^n * n log n) in the worst case.
• Optimal Solution: We iterate through the input array once, which takes O(n) time. For each number, we potentially extend the square streak. In the worst case, we might iterate through all the numbers in the set. However, since we remove each number from the set once it's part of a streak, the overall time complexity for extending streaks is also O(n). Therefore, the dominant factor is the initial iteration and the set operations, making the total time complexity O(n).

Big(O) Space Usage Analysis

• Naive Solution: The space complexity is O(n) in the worst case due to the storage of the subsequence.
• Optimal Solution: We use a set to store the numbers in the input array, which takes O(n) space. Therefore, the space complexity is O(n).

Edge Cases

1. Empty Input: If the input array is empty, we should return -1 since a square streak requires at least two elements.
2. No Square Streak: If there is no square streak in the input, we should return -1.
3. Duplicate Numbers: The algorithm should handle duplicate numbers correctly. For example, [2, 2, 4] should return 2 because [2,4] is a valid square streak.
4. Large Numbers: Ensure that the multiplication of numbers doesn't cause an overflow. Python handles large integers well but consider using modulo if required by the problem's constraints.

def longest_square_streak_handling_edge_cases(nums):
    if not nums:
        return -1

    num_set = set(nums)
    max_len = -1

    for num in nums:
        if num in num_set:
            current_len = 1
            current_num = num
            while current_num * current_num in num_set:
                current_len += 1
                num_set.remove(current_num)
                current_num *= current_num
            
            if current_len >= 2:
                max_len = max(max_len, current_len)

    return max_len if max_len >= 2 else -1