LeetCode 2501. Longest Square Streak in an Array

The task requires us to find the longest subsequence in an integer array where each element, after sorting, is the square of the previous element, with a minimum length of two elements. A subsequence, in this context, is a sequence derived from the array by removing zero or more elements while keeping the remaining elements in the same order. If there is no such subsequence, we should return -1.

Key observations:

  1. The problem’s main requirement is to find a subsequence with specific ordering constraints: after sorting, each element must be the square of its predecessor.
  2. We need to handle arrays of considerable size (up to 10510^5105), which suggests that the solution should be efficient, preferably with a time complexity of O(nlog⁡n)O(n \log n)O(nlogn) or O(n)O(n)O(n).
  3. Since we must validate that each element follows the squaring rule, we can use a hash set for quick lookups to determine if a square of a number is present in the array.

Approach

  1. Sort the Array: Sorting allows us to check each element and look for its possible square in the array.
  2. Use a Hash Set: Store each element in a hash set for O(1)O(1)O(1) time complexity lookups.
  3. Iterate Over Elements: For each number, initialize a streak count and try to find its square in the set. Continue to square and check until no further valid element is found in the streak sequence.
  4. Update the Longest Streak: Keep track of the maximum streak found, ensuring the subsequence length is at least 2.
  5. Return the Result: If a valid streak is found, return its length; otherwise, return -1.

C++ Code Implementation

#include <iostream>
#include <vector>
#include <unordered_set>
#include <algorithm>

int longestSquareStreak(std::vector<int>& nums) {
    // Sort the array for ordered traversal
    std::sort(nums.begin(), nums.end());
    
    // Convert vector to unordered set for O(1) lookups
    std::unordered_set<int> numSet(nums.begin(), nums.end());
    
    int maxStreak = -1;  // Initialize with -1 in case there's no valid streak
    
    // Traverse each element to check possible square streaks
    for (int num : nums) {
        int streak = 1;  // Each number starts a new streak count
        
        // Find the square sequence starting from 'num'
        while (numSet.find(num * num) != numSet.end()) {
            num = num * num;
            streak++;
        }
        
        // Only consider streaks with at least 2 numbers
        if (streak >= 2) {
            maxStreak = std::max(maxStreak, streak);
        }
    }
    
    return maxStreak;
}

int main() {
    std::vector<int> nums1 = {4, 3, 6, 16, 8, 2};
    std::cout << "Output for nums1: " << longestSquareStreak(nums1) << std::endl;
    
    std::vector<int> nums2 = {2, 3, 5, 6, 7};
    std::cout << "Output for nums2: " << longestSquareStreak(nums2) << std::endl;
    
    return 0;
}

Explanation of the Code

  1. Sorting: We sort nums to facilitate ordered traversal and make it easier to find square sequences.
  2. Hash Set for Lookup: Using unordered_set<int> numSet, we efficiently check if a square of a number exists in the array.
  3. Square Streak Calculation: For each number in nums, we attempt to form the longest possible square sequence. If the square of the current number exists in numSet, we update the current number to its square and increase the streak count.
  4. Track Maximum Streak: We update maxStreak if the current streak is longer and meets the minimum length of 2.
  5. Edge Case: If no valid square streak is found, maxStreak remains -1, which is returned accordingly.

Complexity Analysis

  • Time Complexity: Sorting the array takes O(nlog⁡n)O(n \log n)O(nlogn). For each element, checking and computing the square streak is approximately O(n)O(n)O(n) due to quick lookups in the hash set, leading to an overall complexity of O(nlog⁡n)O(n \log n)O(nlogn).
  • Space Complexity: The hash set requires O(n)O(n)O(n) space to store elements.