Skip to content

2501. Longest Square Streak in an Array

Description

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

Solutions

Solution 1: Hash Table + Enumeration

We first use a hash table to record all elements in the array. Then, we enumerate each element in the array as the first element of the subsequence, square this element continuously, and check whether the squared result is in the hash table. If it is, we use the squared result as the next element and continue checking until the squared result is not in the hash table. At this point, we check whether the length of the subsequence is greater than $1$. If it is, we update the answer.

The time complexity is $O(n \times \log \log M)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $\textit{nums}$, and $M$ is the maximum value of the elements in the array $\textit{nums}$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        s = set(nums)
        ans = -1
        for v in nums:
            t = 0
            while v in s:
                v *= v
                t += 1
            if t > 1:
                ans = max(ans, t)
        return ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
class Solution {
    public int longestSquareStreak(int[] nums) {
        Set<Integer> s = new HashSet<>();
        for (int v : nums) {
            s.add(v);
        }
        int ans = -1;
        for (int v : nums) {
            int t = 0;
            while (s.contains(v)) {
                v *= v;
                ++t;
            }
            if (t > 1) {
                ans = Math.max(ans, t);
            }
        }
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
class Solution {
public:
    int longestSquareStreak(vector<int>& nums) {
        unordered_set<long long> s(nums.begin(), nums.end());
        int ans = -1;
        for (int& v : nums) {
            int t = 0;
            long long x = v;
            while (s.count(x)) {
                x *= x;
                ++t;
            }
            if (t > 1) ans = max(ans, t);
        }
        return ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
func longestSquareStreak(nums []int) int {
    s := map[int]bool{}
    for _, v := range nums {
        s[v] = true
    }
    ans := -1
    for _, v := range nums {
        t := 0
        for s[v] {
            v *= v
            t++
        }
        if t > 1 && t > ans {
            ans = t
        }
    }
    return ans
}

Similar to Solution 1, we first use a hash table to record all elements in the array. Then, we design a function $\textit{dfs}(x)$, which represents the length of the square wave starting with $x$. The answer is $\max(\textit{dfs}(x))$, where $x$ is an element in the array $\textit{nums}$.

The calculation process of the function $\textit{dfs}(x)$ is as follows:

  • If $x$ is not in the hash table, return $0$.
  • Otherwise, return $1 + \textit{dfs}(x^2)$.

During the process, we can use memoization, i.e., use a hash table to record the value of the function $\textit{dfs}(x)$ to avoid redundant calculations.

The time complexity is $O(n)$, and the space complexity is $O(n)$. Here, $n$ is the length of the array $\textit{nums}$.

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        @cache
        def dfs(x):
            if x not in s:
                return 0
            return 1 + dfs(x * x)

        s = set(nums)
        ans = max(dfs(x) for x in nums)
        return -1 if ans < 2 else ans

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
class Solution {
    private Map<Integer, Integer> f = new HashMap<>();
    private Set<Integer> s = new HashSet<>();

    public int longestSquareStreak(int[] nums) {
        for (int v : nums) {
            s.add(v);
        }
        int ans = 0;
        for (int v : nums) {
            ans = Math.max(ans, dfs(v));
        }
        return ans < 2 ? -1 : ans;
    }

    private int dfs(int x) {
        if (!s.contains(x)) {
            return 0;
        }
        if (f.containsKey(x)) {
            return f.get(x);
        }
        int ans = 1 + dfs(x * x);
        f.put(x, ans);
        return ans;
    }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
class Solution {
public:
    int longestSquareStreak(vector<int>& nums) {
        unordered_set<long long> s(nums.begin(), nums.end());
        int ans = 0;
        unordered_map<int, int> f;
        function<int(int)> dfs = [&](int x) -> int {
            if (!s.count(x)) return 0;
            if (f.count(x)) return f[x];
            long long t = 1ll * x * x;
            if (t > INT_MAX) return 1;
            f[x] = 1 + dfs(x * x);
            return f[x];
        };
        for (int& v : nums) ans = max(ans, dfs(v));
        return ans < 2 ? -1 : ans;
    }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
func longestSquareStreak(nums []int) (ans int) {
    s := map[int]bool{}
    for _, v := range nums {
        s[v] = true
    }
    f := map[int]int{}
    var dfs func(int) int
    dfs = func(x int) int {
        if !s[x] {
            return 0
        }
        if v, ok := f[x]; ok {
            return v
        }
        f[x] = 1 + dfs(x*x)
        return f[x]
    }
    for _, v := range nums {
        if t := dfs(v); ans < t {
            ans = t
        }
    }
    if ans < 2 {
        return -1
    }
    return ans
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function longestSquareStreak(nums: number[]): number {
    const set = new Set(nums);
    const cache = new Map<number, number>();
    const dfs = (x: number): number => {
        if (cache.has(x)) return cache.get(x)!;
        if (!set.has(x)) return 0;
        cache.set(x, 1 + dfs(x ** 2));
        return cache.get(x)!;
    };

    for (const x of set) dfs(x);
    const ans = Math.max(...cache.values());

    return ans > 1 ? ans : -1;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
function longestSquareStreak(nums) {
    const set = new Set(nums);
    const cache = new Map();
    const dfs = x => {
        if (cache.has(x)) return cache.get(x);
        if (!set.has(x)) return 0;
        cache.set(x, 1 + dfs(x ** 2));
        return cache.get(x);
    };

    for (const x of set) dfs(x);
    const ans = Math.max(...cache.values());

    return ans > 1 ? ans : -1;
}

Solution 3: Counting

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function longestSquareStreak(nums: number[]): number {
    const cnt: Record<number, number> = {};
    const squares = new Set<number>();

    for (const x of new Set(nums)) {
        cnt[x] = (cnt[x] ?? -1) + 1;
        cnt[x ** 2] = (cnt[x ** 2] ?? -1) + 1;
    }

    for (const key in cnt) {
        const x = +key;
        if (cnt[x] || cnt[x ** 2]) {
            squares.add(x);
        }
    }

    if (squares.size <= 1) return -1;

    const iterator = squares[Symbol.iterator]();
    let [max, c, x] = [0, 0, iterator.next().value];

    while (x !== undefined) {
        if (squares.has(x)) {
            squares.delete(x);
            x **= 2;
            c++;
        } else {
            max = Math.max(max, c);
            x = iterator.next().value;
            c = 0;
        }
    }

    return max;
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
function longestSquareStreak(nums) {
    const cnt = {};
    const squares = new Set();

    for (const x of new Set(nums)) {
        cnt[x] = (cnt[x] ?? -1) + 1;
        cnt[x ** 2] = (cnt[x ** 2] ?? -1) + 1;
    }

    for (const key in cnt) {
        const x = +key;
        if (cnt[x] || cnt[x ** 2]) {
            squares.add(x);
        }
    }

    if (squares.size <= 1) return -1;

    const iterator = squares[Symbol.iterator]();
    let [max, c, x] = [0, 0, iterator.next().value];

    while (x !== undefined) {
        if (squares.has(x)) {
            squares.delete(x);
            x **= 2;
            c++;
        } else {
            max = Math.max(max, c);
            x = iterator.next().value;
            c = 0;
        }
    }

    return max;
}

Comments