#2501

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Longest Square Streak in an Array

Find the length of the longest subsequence where each element is a perfect square of its previous one.

array hash table binary search dynamic programming sorting

Problem Statement

You are given an integer array nums. A subsequence is called a square streak if each element is the square of the previous one. The task is to find the length of the longest such subsequence in nums.

Return the length of the longest square streak in nums, or -1 if no such subsequence exists. The subsequence must maintain the order of elements and can be derived by deleting some or no elements from the array.

Examples

Example 1

Input: nums = [4,3,6,16,8,2]

Output: 3

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

There is no square streak in nums so return -1.

Constraints

2 <= nums.length <= 105
2 <= nums[i] <= 105

Solution Approach

Sort and Hash Lookup

Start by sorting the array. This helps to scan through the elements and check if any element is a square of its predecessor using hash lookup, ensuring efficiency. Use a hash set to quickly check for the presence of the square of an element.

Dynamic Programming or Hash Table Tracking

Track subsequences using a hash table where each number points to the length of the longest streak it can form. Iterate through the sorted array and update the streak lengths based on whether an element is a square of the previous element.

Binary Search Optimization

Use binary search to find squares of elements in the sorted array to reduce time complexity. This helps when you are scanning through large datasets, optimizing the search for potential square pairs.

Complexity Analysis

Metric	Value
Time	O(n \cdot \log n)
Space	O(n)

The time complexity of the solution is O(n \cdot \log n) due to the sorting step, and the space complexity is O(n) as we are storing intermediate results in a hash table.

What Interviewers Usually Probe

The candidate should show a clear understanding of the array scanning technique and how hash lookups can optimize the search for subsequences.
An efficient implementation using hash tables or dynamic programming will demonstrate good problem-solving and optimization skills.
Candidates may struggle with the correct approach to binary search optimization, which can lead to an O(n^2) solution if not handled properly.

Common Pitfalls or Variants

Common pitfalls

Forgetting to sort the array first, which can make it impossible to find valid subsequences.
Not using hash lookups effectively, which can lead to excessive computation time when searching for square relationships.
Confusing the problem with simple subsequence length problems, leading to incorrect solutions.

Follow-up variants

Consider variations where the subsequence length could be constrained differently.
What if the subsequence has to be contiguous? That would require additional modifications.
Handle arrays with duplicate elements and ensure they don’t interfere with subsequence counting.

FAQ

What is the primary strategy to solve the Longest Square Streak in an Array problem?

The primary strategy is to scan through the array, sort it, and use hash lookups to find elements that are squares of previous ones.

What happens if there is no valid square streak in the array?

If no square streak exists, return -1 as specified in the problem.

How does the sorting of the array help in this problem?

Sorting the array helps to efficiently find subsequences where each element is a perfect square of the previous one using hash lookups.

What is the time complexity of the solution?

The time complexity is O(n \cdot \log n) due to the sorting step, and the space complexity is O(n) due to the hash table used for tracking subsequences.

Can the solution be optimized further for large arrays?

Yes, using binary search techniques to find the squares of numbers in the sorted array can help optimize the search process.

terminal

Solution

Solution 1: Hash Table + Enumeration

We first use a hash table to record all elements in the array. Then, we enumerate each element in the array as the first element of the subsequence, square this element continuously, and check whether the squared result is in the hash table. If it is, we use the squared result as the next element and continue checking until the squared result is not in the hash table. At this point, we check whether the length of the subsequence is greater than $1$. If it is, we update the answer.

1

2

3

4

5

6

7

8

9

10

11

12

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

Solution 2: Memoization Search

Similar to Solution 1, we first use a hash table to record all elements in the array. Then, we design a function $\textit{dfs}(x)$, which represents the length of the square wave starting with $x$. The answer is $\max(\textit{dfs}(x))$, where $x$ is an element in the array $\textit{nums}$.

1

2

3

4

5

6

7

8

9

10

11

12

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

Continue Practicing

#2713 maximum strictly increasing cells in a matrix #2830 maximize the profit as the salesman #2008 maximum earnings from taxi