Longest Square Streak in an Array — LeetCode 2501 Python Solution

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

Example

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

Python solution

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        s = set(nums)
        ans = -1
        for x in nums:
            t = 0
            while x in s:
                x *= x
                t += 1
            if t > 1:
                ans = max(ans, t)
        return ans

Complexity

Pattern: Binary Search

Halve the search space each step — over an array, or over the answer itself. LeetCode 2501. Longest Square Streak in an Array is filed here because LeetCode tags it Binary Search, which is the vocabulary this hub collects.

The binary search guide has the Python template for the pattern and the 254 LeetCode problems that use it.

Related problems