Leetcode Daily Question 28/10/2024 - 2501. Longest Square Streak in an Array

Problem Description:

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.

from typing import List
class Solution:
  def longestSquareStreak(self, nums: List[int]) -> int:
    max_streak = 0
    nums_set = set(nums)
    nums.sort()
    
    for i in range(len(nums)):
      curr = nums[i]
      streak = 0
      while curr * curr in nums_set:
        curr *= curr
        streak += 1
        
      if streak >= 2:
        max_streak = max(max_streak, streak)
    
    return max_streak if max_streak > 0 else -1

Explanation:

Since the question requires that the streak to be in ascending order. We can first sort the nums array and try every number in num as a start point to see if a possible streak can be formed.

A possible streak is one that is of at least length two, and that every subsequent number is the square of the previous.

Given a start point nums[i], we attempt to continuously square the current number to check the existences of subsequent squares in nums. To make this process space efficient, we can make nums into a set for faster lookup.

def longestSquareStreak(self, nums: List[int]) -> int:
    max_streak = 0
    nums_set = set(nums)
    nums.sort()
    
    for i in range(len(nums)):
      curr = nums[i]
      streak = 0
      while curr * curr in nums_set:
        curr *= curr
        streak += 1
        
      if streak >= 2:
        max_streak = max(max_streak, streak)
    
    return max_streak if max_streak > 0 else -1

The time complexity is O(n log n). The inbuilt sorting method in python takes O(n log n) time. Since for each i, nums[i] does not exceed 10000, the for loop takes O(n) time, meaning the dominating time complexity is O(n log n).

The space complexity is O(n) since we need to store nums as a set for faster lookup.

The full solution can be found near the top of the page.