2501. Longest Square Streak in an Array LeetCode Solution

In this guide, you will get 2501. Longest Square Streak in an Array LeetCode Solution with the best time and space complexity. The solution to Longest Square Streak in an Array problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Table of Contents

1. Problem Statement
2. Complexity Analysis
3. Longest Square Streak in an Array solution in C++
4. Longest Square Streak in an Array solution in Java
5. Longest Square Streak in an Array solution in Python
6. Additional Resources

Problem Statement of Longest Square Streak in an Array

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

Complexity Analysis

• Time Complexity: O(\texttt{sort} + \max(\texttt{nums}))
• Space Complexity: O(\max(\texttt{nums}))

2501. Longest Square Streak in an Array LeetCode Solution in C++

class Solution {
 public:
  int longestSquareStreak(vector<int>& nums) {
    nums.erase(std::unique(nums.begin(), nums.end()), nums.end());
    ranges::sort(nums, greater<>());

    const int maxNum = ranges::max(nums);
    // dp[i] := the longest square streak starts with i
    vector<int> dp(maxNum + 1);

    for (const int num : nums) {
      dp[num] = 1;
      const long squaredNum = static_cast<long>(num) * num;
      if (squaredNum <= maxNum)
        dp[num] += dp[squaredNum];
    }

    const int ans = ranges::max(dp);
    return ans < 2 ? -1 : ans;
  }
};
/* code provided by PROGIEZ */

2501. Longest Square Streak in an Array LeetCode Solution in Java

N/A
// code provided by PROGIEZ

2501. Longest Square Streak in an Array LeetCode Solution in Python

N/A
 # code by PROGIEZ

Additional Resources

• Explore all LeetCode problem solutions at Progiez here
• Explore all problems on LeetCode website here

Happy Coding! Keep following PROGIEZ for more updates and solutions.