# Longest Square Streak in an Array
**Difficulty:** MEDIUM
[External](https://leetcode.com/problems/longest-square-streak-in-an-array)
Canonical: https://scaleengineer.com/dsa/problems/longest-square-streak-in-an-array
**Patterns:** [Dynamic Programming](https://scaleengineer.com/dsa/patterns/dynamic-programming)
**Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search), [Sorting](https://scaleengineer.com/algorithms/sorting)
**Data structures:** Array, Hash Table
---
## 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.

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

**Constraints:**

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

# Approaches
## Sorting and Dynamic Programming
This approach involves sorting the array first and then using dynamic programming to find the longest streak. By sorting the array, we ensure that when we process a number `x`, we have already processed its potential square root `sqrt(x)` if it exists in the array.

We use a hash map to store the length of the longest square streak ending at each number. Let's call this map `dp`. For each number `num` in the sorted array, we check if its square root, `root`, exists. If `root` is an integer and we have already computed the streak length for it (i.e., `root` is in our `dp` map), we can extend that streak. The length of the streak ending at `num` will be `dp[root] + 1`. If `root` doesn't exist or isn't in the map, `num` starts a new streak of length 1. We keep track of the maximum length found during this process.
**Time:** O(N log N) due to the sorting step. The subsequent iteration through the array takes `O(N)` time, with hash map operations taking `O(1)` on average. · **Space:** O(N) in the worst case for the `dp` hash map, which might store an entry for each unique number in `nums`. Sorting can also take up to `O(N)` space depending on the implementation.
**Pros:** Conceptually straightforward application of dynamic programming.; Correctly handles all cases, including duplicates.
**Cons:** The `O(N log N)` time complexity from sorting is not optimal for this problem.; Requires extra space for the hash map and potentially for the sorting algorithm.
### Explanation
The core idea is to build up streaks from smaller numbers to larger numbers. Sorting the input array `nums` allows us to process numbers in increasing order.

We'll use a `HashMap<Integer, Integer>` named `dp`, where `dp[key]` stores the length of the longest square streak ending with the number `key`.

The algorithm proceeds as follows:
1.  Sort the input array `nums` in non-decreasing order.
2.  Initialize a `HashMap<Integer, Integer> dp` to store our dynamic programming states.
3.  Initialize an integer `maxLength = 0` to keep track of the longest streak found so far.
4.  Iterate through each number `num` in the sorted `nums` array.
5.  For each `num`, calculate its integer square root. A simple way to do this is `long root = (long) Math.sqrt(num)`.
6.  Check if `root * root == num`. This confirms that `num` is a perfect square and `root` is its integer square root.
7.  If it is a perfect square, we look up `root` in our `dp` map.
    -   If `dp` contains `root`, it means we can extend the streak ending at `root`. The new streak length for `num` is `dp.get(root) + 1`.
    -   We update `dp.put(num, dp.get(root) + 1)`.
8.  If `num` is not a perfect square or its `root` is not in the `dp` map, it means `num` must start a new streak. The length of this streak is 1.
    -   We set `dp.put(num, 1)`.
9.  After processing `num`, we update our overall maximum length: `maxLength = Math.max(maxLength, dp.get(num))`.
10. After the loop finishes, if `maxLength` is less than 2, no valid streak was found, so we return -1. Otherwise, we return `maxLength`.

```java
import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

class Solution {
    public int longestSquareStreak(int[] nums) {
        Arrays.sort(nums);
        Map<Integer, Integer> dp = new HashMap<>();
        int maxLength = 0;

        for (int num : nums) {
            long root = (long) Math.sqrt(num);
            if (root * root == num && dp.containsKey((int) root)) {
                int prevLength = dp.get((int) root);
                dp.put(num, prevLength + 1);
            } else {
                dp.put(num, 1);
            }
            maxLength = Math.max(maxLength, dp.get(num));
        }

        return maxLength < 2 ? -1 : maxLength;
    }
}
```
### Algorithm
- Sort the input array `nums`.
- Initialize a `HashMap<Integer, Integer> dp` and an integer `maxLength = 0`.
- Iterate through each `num` in the sorted `nums`.
- Calculate the integer square root of `num`, let's call it `root`.
- If `num` is a perfect square and `root` is a key in `dp`:
    - Set `dp[num] = dp[root] + 1`.
- Else:
    - Set `dp[num] = 1`.
- Update `maxLength = max(maxLength, dp[num])`.
- After the loop, if `maxLength < 2`, return -1. Otherwise, return `maxLength`.

## Using a Hash Set for Fast Lookups
A more efficient approach avoids the `O(N log N)` sorting step. The core of the problem is to quickly check if the next number in a potential streak (i.e., the square of the current number) exists in the input array. A `HashSet` is the perfect data structure for this, providing average `O(1)` time complexity for lookups.

We first populate a `HashSet` with all the numbers from the input array to handle duplicates and enable fast lookups. Then, we iterate through each unique number in our set. For each number, we try to build a square streak by repeatedly squaring the number and checking if the result is in the set. We keep track of the length of the current streak and update a global maximum length.
**Time:** O(N). Populating the `HashSet` takes O(N). The main loop iterates through each unique number. For each number, the inner `while` loop runs a very small number of times because the numbers grow exponentially (`x, x^2, x^4, ...`). The number of squaring operations before exceeding the constraint `10^5` is logarithmic in the logarithm of the maximum value, which is effectively constant. Thus, the total time is dominated by the initial set creation and iteration, making it O(N). · **Space:** O(U), where `U` is the number of unique elements in `nums`. In the worst case, this is O(N).
**Pros:** Optimal time complexity of O(N).; The logic is simple and directly models the problem of finding sequences.
**Cons:** Requires O(N) extra space for the HashSet, which might be a concern for very large inputs with memory constraints (though not an issue with the given constraints).
### Explanation
This approach optimizes the search for streak elements. Instead of sorting, we leverage the constant-time average complexity of hash set lookups.

The algorithm is as follows:
1.  Create a `HashSet<Integer>` and add all elements from the `nums` array to it. This automatically handles duplicates and prepares for efficient lookups.
2.  Initialize `maxLength = 0`.
3.  Iterate through each `num` in the `HashSet`.
4.  For each `num`, we treat it as a potential member of a streak and see how long a streak we can form starting from it.
    -   Initialize `currentLength = 1` and `currentNum = num`.
    -   Enter a loop:
        -   Calculate the square: `long square = (long) currentNum * currentNum`. We use `long` to avoid overflow before checking the bounds.
        -   If `square` is larger than the maximum possible value in `nums` (10^5), we can stop.
        -   Check if `(int) square` exists in our `HashSet`.
        -   If it does, we've extended the streak. Increment `currentLength` and update `currentNum = (int) square`.
        -   If it doesn't, the streak starting from our initial `num` ends here. Break the loop.
    -   After the inner loop, update the global maximum: `maxLength = Math.max(maxLength, currentLength)`.
5.  After checking all numbers in the set, if `maxLength` is less than 2, it means no streak of length 2 or more was found. Return -1. Otherwise, return `maxLength`.

An optimization can be made: we only need to start building a streak from a number `x` if `sqrt(x)` is not in the set. This avoids re-calculating streaks. For example, after finding the streak `2, 4, 16`, we don't need to calculate the streak starting from 4 again. This improves practical performance but doesn't change the worst-case time complexity.

```java
import java.util.HashSet;
import java.util.Set;

class Solution {
    public int longestSquareStreak(int[] nums) {
        Set<Integer> numSet = new HashSet<>();
        for (int num : nums) {
            numSet.add(num);
        }

        int maxLength = 0;

        for (int num : numSet) {
            // Optimization: only start from the beginning of a streak
            long root = (long) Math.sqrt(num);
            if (root * root == num && numSet.contains((int) root)) {
                continue; // This number is part of a longer streak, we'll process it then.
            }

            int currentLength = 0;
            long currentNum = num;
            while (numSet.contains((int) currentNum)) {
                currentLength++;
                currentNum = currentNum * currentNum;
                if (currentNum > 100000) { // Constraint check to prevent overflow and unnecessary work
                    break;
                }
            }
            maxLength = Math.max(maxLength, currentLength);
        }

        return maxLength < 2 ? -1 : maxLength;
    }
}
```
### Algorithm
- Create a `HashSet` and populate it with all numbers from `nums`.
- Initialize `maxLength = 0`.
- For each `num` in the `HashSet`:
    - Check if `num` is a good starting point (i.e., its integer square root is not in the set). If not, `continue`.
    - Initialize `currentLength = 0`, `currentNum = num`.
    - While `currentNum` is in the `HashSet`:
        - Increment `currentLength`.
        - Update `currentNum = currentNum * currentNum`.
        - Break if `currentNum` exceeds the maximum possible value.
    - Update `maxLength = max(maxLength, currentLength)`.
- If `maxLength < 2`, return -1. Otherwise, return `maxLength`.

# Solutions
### Java

```java
class Solution {
public
  int longestSquareStreak(int[] nums) {
    Set<Integer> s = new HashSet<>();
    for (int v : nums) {
      s.add(v);
    }
    int ans = -1;
    for (int v : nums) {
      int t = 0;
      while (s.contains(v)) {
        v *= v;
        ++t;
      }
      if (t > 1) {
        ans = Math.max(ans, t);
      }
    }
    return ans;
  }
}

```

### JavaScript

```javascript
/** * @param {number[]} nums * @return {number} */ var longestSquareStreak =
  function (nums) {
    const s = new Set(nums);
    let ans = -1;
    for (const num of nums) {
      let x = num;
      let t = 0;
      while (s.has(x)) {
        x *= x;
        t += 1;
      }
      if (t > 1) {
        ans = Math.max(ans, t);
      }
    }
    return ans;
  };

```

### CPP

```cpp
class Solution {
public:
  int longestSquareStreak(vector<int> &nums) {
    unordered_set<long long> s(nums.begin(), nums.end());
    int ans = -1;
    for (int &v : nums) {
      int t = 0;
      long long x = v;
      while (s.count(x)) {
        x *= x;
        ++t;
      }
      if (t > 1)
        ans = max(ans, t);
    }
    return ans;
  }
};

```

### Python

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

```