Longest Square Streak

XXX. Longest Square Streak

HashSet

Math

Problem Statement:

Find the longest streak of numbers where each number is the perfect square of the previous number.

• Streak must be at least length 2
• Each number must be perfect square of previous
• Return -1 if no valid streak exists

Implementation:

public int longestSquareStreak(int[] nums) {
    // Store all numbers in a set for O(1) lookup
    Set set = new HashSet<>();
    for (int num : nums) {
        set.add(num);
    }

    int max = 0;

    for (int num : nums) {
        // Skip if this number is not start of streak
        int sqrt = (int) Math.sqrt(num);
        if (sqrt * sqrt == num && set.contains(sqrt)) 
            continue;

        // Count length of streak starting from num
        int count = 0;
        long current = num;  // Use long to avoid overflow

        while (set.contains((int) current)) {
            count++;
            current = current * current;

            // Handle integer overflow
            if (current > Integer.MAX_VALUE) 
                break;
        }

        max = Math.max(max, count);
    }

    return max < 2 ? -1 : max;  // Return -1 if no valid streak
}

Complexity:

Time Complexity: O(n * log(M)) where M is max value in nums
Space Complexity: O(n) for HashSet

Key Points:

• **Optimization Techniques**:
  • Use HashSet for O(1) lookups
  • Skip numbers that aren't streak starts
  • Handle integer overflow with long
• **Square Streak Requirements**:
  • Each number in sequence must be perfect square of previous
  • Numbers must exist in original array
  • Minimum length of 2 required
• **Edge Cases**:
  • Handle integer overflow during square calculation
  • Check for perfect squares to avoid duplicate work
  • Validate minimum streak length

Example:

For array [4, 16, 2, 5, 64]:

• Find streaks:
  • 2 → 4 → 16 → 64 (length 4)
  • 4 → 16 → 64 (length 3)
  • 16 → 64 (length 2)
  • 5 (no streak)
• Longest streak: 4 (starting from 2)