Longest Square Streak in an Array

Med

#2282Time: 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.

Patterns

Dynamic Programming

Algorithms

Binary Search Sorting

Data structures

Array Hash Table

Prompt

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 <= 10⁵
2 <= nums[i] <= 10⁵

Approaches

2 approaches with complexity analysis and trade-offs.

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.

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.

Walkthrough

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:

Sort the input array nums in non-decreasing order.
Initialize a HashMap<Integer, Integer> dp to store our dynamic programming states.
Initialize an integer maxLength = 0 to keep track of the longest streak found so far.
Iterate through each number num in the sorted nums array.
For each num, calculate its integer square root. A simple way to do this is long root = (long) Math.sqrt(num).
Check if root * root == num. This confirms that num is a perfect square and root is its integer square root.
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).
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).
After processing num, we update our overall maximum length: maxLength = Math.max(maxLength, dp.get(num)).
After the loop finishes, if maxLength is less than 2, no valid streak was found, so we return -1. Otherwise, we return maxLength.

1import java.util.Arrays;2import java.util.HashMap;3import java.util.Map;4 5class Solution {6    public int longestSquareStreak(int[] nums) {7        Arrays.sort(nums);8        Map<Integer, Integer> dp = new HashMap<>();9        int maxLength = 0;10 11        for (int num : nums) {12            long root = (long) Math.sqrt(num);13            if (root * root == num && dp.containsKey((int) root)) {14                int prevLength = dp.get((int) root);15                dp.put(num, prevLength + 1);16            } else {17                dp.put(num, 1);18            }19            maxLength = Math.max(maxLength, dp.get(num));20        }21 22        return maxLength < 2 ? -1 : maxLength;23    }24}

Complexity

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.

Trade-offs

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.

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.

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.

Walkthrough

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:

Create a HashSet<Integer> and add all elements from the nums array to it. This automatically handles duplicates and prepares for efficient lookups.
Initialize maxLength = 0.
Iterate through each num in the HashSet.
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).
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.

1import java.util.HashSet;2import java.util.Set;3 4class Solution {5    public int longestSquareStreak(int[] nums) {6        Set<Integer> numSet = new HashSet<>();7        for (int num : nums) {8            numSet.add(num);9        }10 11        int maxLength = 0;12 13        for (int num : numSet) {14            // Optimization: only start from the beginning of a streak15            long root = (long) Math.sqrt(num);16            if (root * root == num && numSet.contains((int) root)) {17                continue; // This number is part of a longer streak, we'll process it then.18            }19 20            int currentLength = 0;21            long currentNum = num;22            while (numSet.contains((int) currentNum)) {23                currentLength++;24                currentNum = currentNum * currentNum;25                if (currentNum > 100000) { // Constraint check to prevent overflow and unnecessary work26                    break;27                }28            }29            maxLength = Math.max(maxLength, currentLength);30        }31 32        return maxLength < 2 ? -1 : maxLength;33    }34}

Complexity

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

Trade-offs

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

Solutions

Solution

1class Solution {2public3  int longestSquareStreak(int[] nums) {4    Set<Integer> s = new HashSet<>();5    for (int v : nums) {6      s.add(v);7    }8    int ans = -1;9    for (int v : nums) {10      int t = 0;11      while (s.contains(v)) {12        v *= v;13        ++t;14      }15      if (t > 1) {16        ans = Math.max(ans, t);17      }18    }19    return ans;20  }21}

1/** * @param {number[]} nums * @return {number} */ var longestSquareStreak =2  function (nums) {3    const s = new Set(nums);4    let ans = -1;5    for (const num of nums) {6      let x = num;7      let t = 0;8      while (s.has(x)) {9        x *= x;10        t += 1;11      }12      if (t > 1) {13        ans = Math.max(ans, t);14      }15    }16    return ans;17  };

1class Solution {2public:3  int longestSquareStreak(vector<int> &nums) {4    unordered_set<long long> s(nums.begin(), nums.end());5    int ans = -1;6    for (int &v : nums) {7      int t = 0;8      long long x = v;9      while (s.count(x)) {10        x *= x;11        ++t;12      }13      if (t > 1)14        ans = max(ans, t);15    }16    return ans;17  }18};

1class Solution:2    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

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem