Skip to content

2501. Longest Square Streak in an Array 👍

  • Time: $O(\texttt{sort} + \max(\texttt{nums}))$
  • Space: $O(\max(\texttt{nums}))$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
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;
  }
};