• Leetcode POTDs

Problem 2501 Longest Square Streak in an Array

Problem Statement

Link - Problem 2501

Question

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 eleme

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 <= 10⁵
• 2 <= nums[i] <= 10⁵

Solution

class Solution {
public:
    int longestSquareStreak(vector<int>& nums) {
        vector<bool> check_vector(100001, false);
        for(int num : nums) {
                check_vector[num] = true;
        }

        int max_len = -1;

        for(int num : nums) {
            int len = 1;
            long val = num;
            if (val > 317) { // sqrt(100000) is around 317, so beyond this limit, squares exceed 100000
                continue;
            }

            while (val * val <= 100000 && check_vector[val * val]) {
                len++;
                max_len = max(max_len, len);
                val = val * val;
            }
        }
        return max_len;
    }
};

Complexity Analysis

| Algorithm                 | Time Complexity | Space Complexity |
| ------------------------- | --------------- | ---------------- |
| Creating a set for lookup | O(N)            | O(N)             |
| Iteration and checking    | O(N)            | O(1)             |
| Total                     | O(N)            | O(N)             |

Explanation

If a subsequence can be sorted after picking the elements, then its equivalent to sorting the parent array and then picking the elements.

1. Intuition

• Even though the question is saying subsequences, its just misleading.
• The actual question doesnt care about the order of the elements. Hence sorting also works.
• But to check if we can find a chain of squares, we need to look up the elements present in the array in O(1) time.
• Hence we can use a boolean array to store the presence of the elements.
• Then for every element, we can check if we can find a chain of squares starting from that element.
• If we can, we can update the maximum length of the chain.
• One more micro-optimization is to check if the square of the element is greater than 100000 then we can skip that element as the square of that element will be greater than 100000. This is because the maximum element in the array is 100000 according to the constraints.
• Hence we can skip that element and move to the next element.
• This way we can find the maximum length of the chain of squares.

2. Implementation

- Create a boolean array `check_vector` of size 100001 and initialize all elements to `false`.
- Iterate over the elements of the array and set the corresponding index in the `check_vector` to `true`.
- Initialize the variable `max_len` to -1.
  This variable will store the maximum length of the chain of squares.
- Iterate over the elements of the array.
  - Initialize the variable `len` to 1.
    This variable will store the length of the chain of squares starting from the current element.
  - Initialize the variable `val` to the current element.
  - Check if the square of the current element is greater than 317.
  - If it is, then skip the current element and move to the next element.
    - While the square of the current element is less than or equal to 100000
      and the square of the current element is present in the `check_vector`,
      - increment the `len` variable
      - Update the `max_len` variable with the maximum of the current `len` and `max_len`.
      - Update the `val` variable with the square of the current element.
- Return the `max_len` variable.

This is a relatively simple problem that can be solved using a set for lookup and iteration over the elements of the array. The time complexity of the solution is O(N), where N is the number of elements in the array, and the space complexity is O(N) for the set used for lookup.