Longest Square Streak in an Array - Practice Coding Problems

Longest Square Streak in an Array - Problem

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.

Input & Output

Example 1 — Perfect Square Chain

$ Input: nums = [4,3,6,16,8,2]

› Output: 3

💡 Note: We can form the square streak [2,4,16]: 2² = 4, 4² = 16. The longest streak has length 3.

Example 2 — No Valid Streak

$ Input: nums = [2,3,5,6,7]

› Output: -1

💡 Note: No number in the array has its square also in the array, so no square streak can be formed.

Example 3 — Multiple Short Streaks

$ Input: nums = [2,4,8,16]

› Output: 2

💡 Note: We can form [2,4] and [4,16] but not [2,4,16] since 4² = 16 but 2² = 4 ≠ 8. Max length is 2.

Constraints

2 ≤ nums.length ≤ 10⁵
-10⁵ ≤ nums[i] ≤ 10⁵

Visualization

Tap to expand

Understanding the Visualization

Input Array

Array of integers that may contain square relationships

Find Chains

Identify sequences where each number is square of previous

Return Length

Length of longest valid chain, or -1 if none exist

Key Takeaway

🎯 Key Insight: Use hash set for O(1) lookups and build chains by squaring numbers until no next square exists

Asked in

f Meta 15 G Google 12 a Amazon 8

The key insight is to use a hash set for O(1) lookups and build chains by repeatedly squaring numbers. The optimal approach uses memoization to avoid recalculating chain lengths. Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Set Optimization	O(n × k)	O(n)	Use hash set to quickly check if squares exist, build chains from each number
Brute Force - Check All Subsequences	O(n × 2^n)	O(n)	Generate all possible subsequences and check if they form square streaks
Dynamic Programming with Memoization	O(n)	O(n)	Use memoization to avoid recalculating chain lengths from same starting points

Hash Set Optimization — Algorithm Steps

Store all numbers in a hash set
For each number, try building a chain by squaring
Track the maximum chain length found

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Set

Store all numbers in hash set for O(1) lookup

Try Chains

For each number, try building chain by squaring

Find Max

Track the longest valid chain found

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NUMS 100000

int solution(int* nums, int numsSize) {
    // Use a simple array as hash set for positive numbers
    int hash[MAX_NUMS] = {0};
    
    // Mark all numbers as present
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] >= 0 && nums[i] < MAX_NUMS) {
            hash[nums[i]] = 1;
        }
    }
    
    int maxLength = -1;
    
    for (int i = 0; i < numsSize; i++) {
        if (nums[i] < 0 || nums[i] >= MAX_NUMS) continue;
        
        // Try to build chain starting from this number
        long long current = nums[i];
        int length = 1;
        
        while (current * current < MAX_NUMS && hash[current * current]) {
            current = current * current;
            length++;
        }
        
        if (length >= 2) {
            if (length > maxLength) {
                maxLength = length;
            }
        }
    }
    
    return maxLength;
}

int main() {
    char line[1000];
    fgets(line, sizeof(line), stdin);
    
    // Parse JSON array manually
    int nums[20];
    int numsSize = 0;
    char* token = strtok(line + 1, ",]");
    
    while (token != NULL && numsSize < 20) {
        nums[numsSize++] = atoi(token);
        token = strtok(NULL, ",]");
    }
    
    int result = solution(nums, numsSize);
    printf("%d\n", result);
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n × k)

For each of n numbers, build chain of max length k (k ≤ 5 due to integer constraints)

✓ Linear Growth

Space Complexity

O(n)

Hash set stores all n numbers

⚡ Linearithmic Space

32.0K Views

Medium Frequency

~25 min Avg. Time

850 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Set Optimization — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler