Longest square streak in an array

Array Hash Table Binary Search Dynamic Programming Sorting

53.1% acceptance

Feb 25, 2026

1008

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.

Solution

Rust

Time O(n)

Space O(n)

LeetCode

solution.rs

impl Solution {
  pub fn longest_square_streak(nums: Vec<i32>) -> i32 {
    use std::collections::{HashMap, HashSet};
    let set: HashSet<i64> = nums.iter().map(|&x| x as i64).collect();
    let mut memo: HashMap<i64, i32> = HashMap::new();

    fn dfs(n: i64, set: &HashSet<i64>, memo: &mut HashMap<i64, i32>) -> i32 {
      if let Some(&v) = memo.get(&n) {
        return v;
      }
      let sq = n * n;
      let res = if set.contains(&sq) {
        1 + dfs(sq, set, memo)
      } else {
        1
      };
      memo.insert(n, res);
      res
    }

    let mut ans = -1;
    for &n in &set {
      let len = dfs(n, &set, &mut memo);
      if len >= 2 {
        ans = ans.max(len);
      }
    }
    ans
  }
}