You are given an integer array nums. A subsequence of nums is called a square streak if:
2, andReturn 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] <= 105This approach leverages a HashSet for quick access to elements and checks subsequent squares in the sequence. We iterate over each number in the array, and for each number, keep finding its squares while incrementing the length of the streak. The longest streak is tracked and returned at the end.
The program begins by defining a helper function contains to determine if a squared value exists in the array. Then, for each element in the array, it calculates the squares sequentially. It keeps track of the maximum streak length, which is updated whenever a longer streak is found.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^1.5) in worst-case due to nested loops and nested search.
Space Complexity: O(1) extra space for auxiliary storage as in-place checks are performed.
This approach uses dynamic programming to store intermediate results regarding the longest square streak ending at each number. Sorting the array helps in ensuring that every subsequent square evaluated is in a larger-than relationship compared to previous elements, thus contributing to the streak length.
The C solution uses a dynamic programming array dp where each entry keeps track of the longest sequence ending with that element. It sorts the input array to facilitate streak calculations, checking possible backward links with previous elements.
C++
Java
Python
C#
JavaScript
Time Complexity: O(n^2) due to nested loops used in the calculation of dp array.
Space Complexity: O(n) for managing the dp array.
| Approach | Complexity |
|---|---|
| HashSet Based Approach | Time Complexity: O(n^1.5) in worst-case due to nested loops and nested search. |
| Dynamic Programming Approach | Time Complexity: O(n^2) due to nested loops used in the calculation of dp array. |
Longest Square Streak in an Array | Detailed Approaches | Dry Run | Leetcode 2501 | codestorywithMIK • codestorywithMIK • 7,282 views views
Watch 9 more video solutions →Practice Longest Square Streak in an Array with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor