How do you solve Longest Square Streak in an Array on LeetCode?

Longest Square Streak in an Array (LeetCode #2501) can be solved using Brute Force or Optimal Solution. The optimal approach is Optimal Solution with O(n log n) time complexity and O(n) space complexity. Key insight: Using a set allows for quick lookups to check if a square exists.

What is the brute force solution for Longest Square Streak in an Array?

The brute force approach for Longest Square Streak in an Array is Brute Force, with O(n²) time complexity and O(1) space complexity. The brute force approach involves generating all possible subsequences of the array and checking each one to see if it forms a square streak. This is simple but inefficient due to the exponential number of subsequences. The optimal Optimal Solution approach improves this to O(n log n).

What are the interview tips for Longest Square Streak in an Array?

Always start with a brute force solution to understand the problem better. Make sure to explain your thought process clearly while coding. Consider edge cases early, such as arrays with no valid square streaks.

What are common mistakes when solving Longest Square Streak in an Array?

Not considering all possible subsequences and missing valid square streaks. Failing to check for the minimum length of 2 for a valid square streak.

#2501

Longest Square Streak in an Array

Medium

ArrayHash TableBinary SearchDynamic ProgrammingSortingHash MapArray

LeetCode ↗

Approaches

Brute ForceOptimal

Complexity Comparison

	Brute Force	Optimal Solution★
Time	O(n²)	O(n log n)
Space	O(1)	O(n)

💡

Intuition

Time O(n log n)Space O(n)

The optimal approach uses a set to store the numbers for quick lookups and iterates through the sorted array to build square streaks. This is efficient because it avoids generating all subsequences and directly checks for valid square relationships.

⚙️

Algorithm

4 steps

1Step 1: Store all elements of nums in a set for O(1) lookups.
2Step 2: Sort the array nums.
3Step 3: Iterate through the sorted array and for each number, check if its square exists in the set.
4Step 4: Keep a count of the current streak length and update the maximum streak length found.

solution.py17 lines

1# Full working Python code
2
3def longest_square_streak(nums):
4    num_set = set(nums)
5    nums.sort()
6    max_length = -1
7    current_length = 0
8
9    for num in nums:
10        if current_length == 0 or num == nums[current_length - 1] ** 2:
11            current_length += 1
12        else:
13            current_length = 1 if num in num_set else 0
14        if current_length >= 2:
15            max_length = max(max_length, current_length)
16
17    return max_length if max_length >= 2 else -1

ℹ

Complexity note: The sorting step takes O(n log n) time, and storing elements in a set takes O(n) space. The iteration through the array is O(n), making this approach efficient.

1Using a set allows for quick lookups to check if a square exists.
2Sorting the array helps in easily checking the square relationships in order.

Solutions and explanations are original Tejav content. Problem titles © LeetCode — use the LeetCode button above for the full problem statement.