Problem

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.

Examples

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.

Solution

Method 1 - Sorting and using set

Here is the approach:

  1. Sort the array to easily find subsequences where each element is the square of the previous one.
  2. Use a set for quick lookup of elements.
  3. Iterate through the sorted array and for each element, keep squaring it and checking if the square exists in the set.
  4. Keep track of the longest length of such subsequences.

Video explanation

Here is the video explaining this method in detail. Please check it out:

Code

Java
Not removing the elements from set
class Solution {
    public int longestSquareStreak(int[] nums) {
        Arrays.sort(nums);
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        
        int ans = -1;
        for (int num : nums) {
            int len = 0;
            long curr = num;
            while (numSet.contains((int) curr)) {
                len++;
                numSet.remove((int) curr);
                curr = curr * curr;
                if (curr > Integer.MAX_VALUE) {
                    break; // to avoid overflow
                }
            }
            if (len >= 2) {
                ans = Math.max(ans, len);
            }
        }
        return ans;
    }
}
Removing the elements from set once counted
class Solution {
    public int longestSquareStreak(int[] nums) {
        Arrays.sort(nums);
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }
        
        int ans = -1;
        for (int num : nums) {
            if (!numSet.contains(num)) {
                continue;
            }
            
            int len = 0;
            long curr = num;
            while (numSet.contains((int) curr)) {
                len++;
                numSet.remove((int) curr);
                curr = curr * curr;
                if (curr > Integer.MAX_VALUE) break; // to avoid overflow
            }
            if (len >= 2) {
                ans = Math.max(ans, len);
            }
        }
        return ans;
    }
}
Python
class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        nums.sort()
        num_set = set(nums)
        ans = -1
        
        for num in nums:
            ln = 0
            curr = num
            while curr in num_set:
                ln += 1
                num_set.remove(curr)
                curr = curr * curr
                if curr > (1 << 31) - 1:  # avoid overflow, equivalent to Integer.MAX_VALUE
                    break
            if ln >= 2:
                ans = max(ans, ln)
        
        return ans
Removing
 class Solution:
     def longestSquareStreak(self, nums: List[int]) -> int:
         nums.sort()
         num_set = set(nums)
         ans = -1
         
         for num in nums:
             if num not in num_set:
                 continue
             
             ln = 0
             curr = num
             while curr in num_set:
                 ln += 1
                 num_set.remove(curr)
                 curr = curr * curr
                 if curr > (1 << 31) - 1:  # avoid overflow, equivalent to Integer.MAX_VALUE
                     break
             if ln >= 2:
                 ans = max(ans, ln)
         
         return ans

Complexity

  • ⏰ Time complexity: O(n (log n),
  • O(n log n) for sorting the array nums and then adding elements to set takes O(n) time, and finally checking subsequence roughly takes O(n) time as we are making quadratic jumps to find the next power.
  • 🧺 Space complexity: O(n), for storing elements in a set.