2501. 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.

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 <= 105
• 2 <= nums[i] <= 105

Approach 01:

class Solution {
public:
    int longestSquareStreak(vector<int>& numbers) {
        // Remove duplicates and sort in descending order
        numbers.erase(std::unique(numbers.begin(), numbers.end()), numbers.end());
        ranges::sort(numbers, greater<>());

        const int maxNumber = ranges::max(numbers);
        // dp[i] represents the longest square streak starting with i
        vector<int> dp(maxNumber + 1);

        for (const int number : numbers) {
            dp[number] = 1;
            const long squaredNumber = static_cast<long>(number) * number;
            if (squaredNumber <= maxNumber)
                dp[number] += dp[squaredNumber];
        }

        const int result = ranges::max(dp);
        return result < 2 ? -1 : result;
    }
};

class Solution:
    def longestSquareStreak(self, numbers: list[int]) -> int:
        # Remove duplicates and sort in descending order
        numbers = sorted(set(numbers), reverse=True)

        maxNumber = max(numbers)
        # dp[i] represents the longest square streak starting with i
        dp = [0] * (maxNumber + 1)

        for number in numbers:
            dp[number] = 1
            squaredNumber = number * number
            if squaredNumber <= maxNumber:
                dp[number] += dp[squaredNumber]

        result = max(dp)
        return -1 if result < 2 else result

Time Complexity

• Removing duplicates:

  The function uses unique and erase to remove duplicates, which takes \(O(n)\), where \(n\) is the number of elements in the input array.

• Sorting the array in descending order:

  The function sorts the array, which has a time complexity of \(O(n \log n)\), where \(n\) is the number of elements in the array.

• Iterating through the array:

  The function then iterates over the array to calculate the longest square streak for each number. This loop takes \(O(n)\).

• Calculating square values:

  For each element in the array, the function checks whether the square of that element is within bounds and updates the dynamic programming array. This operation involves checking one square for each element, which takes constant time \(O(1)\) for each element. Thus, this loop also takes \(O(n)\).

• Finding the maximum:

  After processing the array, the function uses ranges::max to find the maximum value in the dynamic programming array, which takes \(O(n)\).

• Overall Time Complexity:

  The overall time complexity is \(O(n \log n)\), where \(n\) is the number of elements in the input array. The sorting step dominates the time complexity.

Space Complexity

• Space used by the dynamic programming array:

  The function creates a dynamic programming array of size maxNumber + 1, where maxNumber is the largest number in the array. Therefore, the space complexity for this array is \(O(maxNumber)\).

• Space used by the input array:

  Since the function modifies the input array in place (removing duplicates and sorting), no extra space is used for the input array beyond its initial size \(O(n)\).

• Overall Space Complexity:

  The space complexity is \(O(maxNumber)\), which can be considered \(O(n)\) in the worst case if all elements are unique and range up to \(n\).