Longest Square Streak in an Array - Video Solutions
Longest Square Streak in an Array | Detailed Approaches | Dry Run | Leetcode 2501 | codestorywithMIK
Longest Square Streak in an Array - Video Solution
Watch 10 video solutions for Longest Square Streak in an Array, a medium level problem involving Array, Hash Table, Binary Search. This walkthrough by codestorywithMIK has 7,854 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
Problem Statement
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 <= 1052 <= nums[i] <= 105
Approach Overview
Problem Overview: You are given an integer array and need the length of the longest sequence where every next number equals the square of the previous one. For example, a chain like 2 → 4 → 16 → 256. The sequence must exist entirely inside the array, and if the longest chain has length less than 2, the answer is -1.
Approach 1: HashSet Based Approach (O(n log M) time, O(n) space)
Store all numbers in a HashSet for O(1) membership checks. For each number, repeatedly square the current value and check if the squared value exists in the set. Continue extending the chain until the square is missing. Track the maximum length seen across all starting values. The key insight is constant-time lookup using a hash structure, which makes chain expansion efficient. This approach works well for unsorted arrays and is a natural application of a hash table with basic iteration over an array.
Approach 2: Dynamic Programming with Sorting (O(n log n) time, O(n) space)
Sort the array first so smaller values are processed before their squares. Maintain a map dp[num] representing the longest square chain ending at num. For each value, compute its integer square root. If the root exists in the map and root * root == num, extend the chain with dp[num] = dp[root] + 1. Otherwise start a new chain with length 1. Sorting ensures the potential predecessor appears earlier, allowing a clean bottom‑up dynamic programming transition. This approach avoids repeatedly exploring the same chains and keeps updates predictable.
Recommended for interviews: The HashSet approach is typically the fastest to implement and demonstrates strong understanding of constant-time lookups and sequence expansion. Interviewers often expect this idea because it directly models the square relationship. The DP + sorting approach shows deeper algorithmic thinking by building results incrementally and avoiding redundant chain exploration. Knowing both approaches signals strong problem-solving depth.
Complexity Analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet Based Approach | O(n log M) | O(n) | General case when the array is unsorted and fast membership checks are needed |
| Dynamic Programming with Sorting | O(n log n) | O(n) | When building chains incrementally after sorting or when avoiding repeated chain traversal |