2501. Longest Square Streak in an Array
Problem Description
In this problem, we are given an integer array nums
. We need to find a particular type of subsequence known as a "square streak." A square streak has the following characteristics:
- It has a length of at least 2 elements.
- When sorted, each element of the subsequence, except for the first, is the square of the previous element.
Our goal is to figure out the length of the longest square streak in nums
. If no square streak exists, we return -1.
A subsequence can be understood as a sequence that can be obtained from the original array by removing some elements (possibly, none) without changing the order of the remaining elements.
Intuition
The solution approach involves iterating through each element in the integer array nums
and attempting to construct the longest square streak starting from that element. To achieve this, we use the following intuition and steps:
-
First, we convert the list of numbers into a set
s
for faster lookups. Checking if an item is in a set is faster than checking if it is in a list because sets in Python are implemented as hash tables. -
For each number
v
in the array, we initialize a temporary countert
to zero. This counter will be used to track the length of the square streak starting withv
. -
We then enter a while loop that continuously squares
v
and checks whether the newv
is in the sets
. If it is found, it means we can continue the square streak, and we increment the countert
by one. -
The loop stops when the squared number is no longer in the set, indicating the streak cannot be extended further.
-
If the counter
t
is greater than 1, meaning we have found a square streak, we compare it with our current answerans
and updateans
with the maximum value. -
Finally, after we have checked all numbers, we return the value of
ans
.
This brute-force approach works because it tries to extend a square streak from each number in the array. However, it may not be optimal for very large arrays, as the time complexity is proportional to the number of elements times the length of the longest streak.
Learn more about Binary Search, Dynamic Programming and Sorting patterns.
Solution Approach
The solution approach involves a few key steps, using a set for fast element lookup and a simple iteration pattern to build potential square streaks.
Here's a detailed walk-through of the implementation:
-
Create a Set for Fast Lookups: The algorithm begins by converting the list
nums
into a sets
. This transformation is done to take advantage of the constant time complexityO(1)
for checking if an element is present in the set. -
Iterate Over the Array: For each element
v
innums
, we try to find the longest square streak starting with that number. -
Initialize a Counter: For each
v
, we set a countert
to zero. This counter will track the length of the streak. -
While Loop to Extend the Streak: We then enter a loop that continues as long as
v
is in the sets
. Within this loop, we do two things:- Square
v
by settingv = v * v
. This is based on the rule for the square streak where each following number must be the square of its predecessor. - Increment the counter
t
by 1 to denote that the streak has been extended by another element.
- Square
-
Check Streak Validity: After the loop ends, we check if
t > 1
to ensure that the streak constitutes at least two elements (as single-element streaks are not valid). -
Update Maximum Streak Length: If a valid streak is found, we compare
t
with the current maximum streak lengthans
, updatingans
withmax(ans, t)
if necessary. -
Return the Result: After iterating through all elements in
nums
, if any square streak was found,ans
would be greater than -1. If no streak was found,ans
would be -1, which is then returned as the result.
1class Solution:
2 def longestSquareStreak(self, nums: List[int]) -> int:
3 s = set(nums)
4 ans = -1
5 for v in nums:
6 t = 0
7 while v in s:
8 v *= v # Square the current number
9 t += 1 # Increment the streak length
10 if t > 1: # If the streak contains at least 2 elements
11 ans = max(ans, t) # Update the maximum streak length
12 return ans
By applying these steps, the solution manages to identify the longest square streak effectively without the need for sorting or additional complex data structures.
Ready to land your dream job?
Unlock your dream job with a 2-minute evaluator for a personalized learning plan!
Start EvaluatorExample Walkthrough
Let's go through an example to illustrate the solution approach described above using the following array of integers:
nums = [1, 16, 4, 2, 64]
Following the algorithm steps:
-
Create a Set for Fast Lookups: We convert
nums
into a sets
for fast element lookup. So,s = {1, 16, 4, 2, 64}
. -
Iterate Over the Array: We begin iterating with
v = 1
. -
Initialize a Counter: We set a temporary counter
t = 0
. This will track the length of a potential square streak. -
While Loop to Extend the Streak: We check if
v = 1
is ins
. It is, so we enter the loop.- We square
v
to get1 * 1 = 1
and since1
is still in the sets
, we incrementt
to 1.
Since squaring
v = 1
yields the same number, we end up in an infinite loop. To mitigate this, our approach should check if the squared number is different from the current number before looping. Here, we would need to add a condition to the loop to continue only if the squaredv
is different fromv
.-
Now, we should have
v = 1
, andt
does not increase further as we are trapped in a loop where the value ofv
doesn't change. -
To correct the algorithm and continue the example, we should stop incrementing
t
once we notice thatv*v
does not produce a new number.
- We square
-
Check Streak Validity: We observe that after correcting the loop,
t = 1
, which means no streak found, as the streak must be at least 2 numbers long. -
Iterate Over the Next Array Element:
v = 16
- Initialize
t = 0
. 16
is ins
, squarev
to get256
. Since256
is not ins
, we stop the loop.t
remains 0 since16
is not the beginning of a square streak within the set.
- Initialize
-
Repeat the Process:
-
For
v = 4
, we initializet = 0
. Squaringv
yields16
, which is ins
. Incrementt
to 1. Squaring again yields256
, which is not ins
, so we stop here.t
is 1, so no valid streak. -
With
v = 2
, square it to get4
, which is ins
. Incrementt
to 1. Square4
to get16
, which is ins
. Incrementt
to 2. Square16
to get256
, which is not ins
, break.t
is now 2, so we have found a valid streak of length 2. We setans
to 2 as it's the maximum so far. -
For
v = 64
, we square it to get4096
, which is not ins
, so the streak does not start here.
-
-
Return the Result: After completing the iteration, the longest square streak found has a length of 2 (starting with
v = 2
), and hence we returnans = 2
.
Please note that the provided Python code in the original problem description had an issue where it could lead to an infinite loop if v
squared did not yield a different number. An additional loop condition is necessary to prevent that, and the corrected example assumes that this change has been made.
Solution Implementation
1class Solution:
2 def longest_square_streak(self, nums):
3 """
4 This function computes the longest streak of squaring operations
5 that can be performed on elements of the input list before a number
6 is reached that is not present in the list.
7
8 Args:
9 nums (List[int]): List of integers on which the square streak will be performed.
10
11 Returns:
12 int: The length of the longest possible streak of squaring operations.
13 """
14 # Convert the list to a set for O(1) containment checks
15 num_set = set(nums)
16 # Initialize the answer to -1, useful for cases where no streak found
17 max_streak = -1
18
19 # Iterate over all numbers in the input list
20 for num in nums:
21 # Initialize streak counter for the current number
22 streak_length = 0
23 # Continuously square the number and check if the squared number is in the list
24 while num in num_set:
25 num = num ** 2 # Square the number
26 streak_length += 1 # Increment the streak length
27
28 # Update the maximum streak length if the current streak is longer
29 # Only consider streaks with more than one squaring operation
30 if streak_length > 1:
31 max_streak = max(max_streak, streak_length)
32
33 # Return the longest streak found
34 return max_streak
35
1class Solution {
2
3 // Method to find the longest streak of squaring operations until
4 // a number no longer exists within the set
5 public int longestSquareStreak(int[] nums) {
6 // Initialize a HashSet to store the unique numbers from the array
7 Set<Integer> uniqueNumbers = new HashSet<>();
8
9 // Populate the set with values from the nums array
10 for (int value : nums) {
11 uniqueNumbers.add(value);
12 }
13
14 // Initialize the answer as -1, assuming no such streak is found by default
15 int longestStreak = -1;
16
17 // Iterate over the array to calculate the square streaks for each number
18 for (int value : nums) {
19 // Initialize a temporary streak counter
20 int currentStreak = 0;
21
22 // Continue squaring the current number and checking its existence in the set
23 while (uniqueNumbers.contains(value)) {
24 value = value * value; // Square the number
25 currentStreak++; // Increment the streak count
26 }
27
28 // Only consider streaks that consist of at least 2 numbers
29 if (currentStreak > 1) {
30 // Update the longest streak if the current streak is longer
31 longestStreak = Math.max(longestStreak, currentStreak);
32 }
33 }
34
35 // Return the result containing the longest squaring streak
36 return longestStreak;
37 }
38}
39
1#include <functional>
2#include <queue>
3
4// Definition for a binary tree node.
5struct TreeNode {
6 int val;
7 TreeNode *left;
8 TreeNode *right;
9 // Constructor to create a leaf node with value 'x'
10 TreeNode(int x) : val(x), left(nullptr), right(nullptr) {}
11 // Constructor to create a node with value 'x' and given left and right children
12 TreeNode(int x, TreeNode *left, TreeNode *right) : val(x), left(left), right(right) {}
13};
14
15class Solution {
16public:
17 // Counts the number of nodes in the binary tree such that
18 // the count of nodes greater than or equal to it in the path from
19 // it to the root is at least 'k'
20 int countNodesWithValueGreaterOrEqual(TreeNode* root, int k) {
21 int count = 0; // Initialize the count of nodes to zero
22
23 // A depth-first search (DFS) function that is used to traverse the tree
24 // This function uses a lambda expression and returns a priority queue with the
25 // k highest values in the path from current node to the root
26 std::function<std::priority_queue<int>(TreeNode*)> dfs = [&](TreeNode* node) -> std::priority_queue<int> {
27 // If the node is null, return an empty priority queue
28 if (!node) {
29 return std::priority_queue<int>();
30 }
31
32 // Recursively apply DFS to the left and right subtrees
33 std::priority_queue<int> leftQueue = dfs(node->left);
34 std::priority_queue<int> rightQueue = dfs(node->right);
35
36 // Merge the two queues by moving all elements from the right queue to the left queue
37 while (!rightQueue.empty()) {
38 leftQueue.push(rightQueue.top());
39 rightQueue.pop();
40
41 // Ensure the size of the left queue does not exceed 'k'
42 if (leftQueue.size() > k) {
43 leftQueue.pop();
44 }
45 }
46
47 // If the size of the left queue is exactly 'k' and the smallest element in it
48 // is smaller than the current node's value, increment the count
49 if (leftQueue.size() == k && leftQueue.top() < node->val) {
50 ++count;
51 }
52
53 // Add the current node's value to the priority queue
54 leftQueue.push(node->val);
55
56 // Ensure the size of the priority queue does not exceed 'k' by removing
57 // the smallest element if necessary
58 if (leftQueue.size() > k) {
59 leftQueue.pop();
60 }
61
62 // Return the priority queue representing the k highest values from
63 // current node to the root
64 return leftQueue;
65 };
66
67 // Perform a DFS starting from the root
68 dfs(root);
69
70 // Return the final count of nodes fulfilling the criteria
71 return count;
72 }
73};
74
1// Definition for a binary tree node.
2class TreeNode {
3 val: number;
4 left: TreeNode | null;
5 right: TreeNode | null;
6
7 // Constructor to create a node
8 constructor(val: number, left: TreeNode | null = null, right: TreeNode | null = null) {
9 this.val = val;
10 this.left = left;
11 this.right = right;
12 }
13}
14
15// Initialize the count of nodes to zero as a global variable
16let count: number = 0;
17
18// Type definition for a priority queue in TypeScript
19type PriorityQueue = number[];
20
21// Depth-first search (DFS) function that traverses the tree
22// It uses a lambda expression and returns a priority queue with the
23// k highest values in the path from the current node to the root
24const dfs = (node: TreeNode | null, k: number): PriorityQueue => {
25 // If the node is null, return an empty priority queue
26 if (!node) {
27 return [];
28 }
29
30 // Recursively apply DFS to the left and right children
31 let leftQueue: PriorityQueue = dfs(node.left, k);
32 let rightQueue: PriorityQueue = dfs(node.right, k);
33
34 // Merge two queues by moving all elements from the right queue to the left queue
35 while (rightQueue.length) {
36 leftQueue.push(rightQueue.shift()!);
37 leftQueue = leftQueue.sort((a, b) => b - a); // Sort to maintain max-heap property
38
39 // Ensure the size of the left queue does not exceed 'k'
40 if (leftQueue.length > k) {
41 leftQueue.pop();
42 }
43 }
44
45 // If the size of the left queue is exactly 'k' and the smallest element in it
46 // is smaller than the current node's value, increment the count
47 if (leftQueue.length === k && leftQueue[leftQueue.length - 1] < node.val) {
48 count++;
49 }
50
51 // Add the current node's value to the priority queue
52 leftQueue.push(node.val);
53
54 // Ensure the size of the priority queue does not exceed 'k' by removing
55 // the smallest element if necessary
56 if (leftQueue.length > k) {
57 leftQueue.pop();
58 }
59
60 // Return the priority queue representing the k highest values from
61 // the current node to the root
62 return leftQueue;
63};
64
65// Function to count the number of nodes in the binary tree such that
66// the count of nodes greater than or equal to it in the path from
67// it to the root is at least 'k'
68const countNodesWithValueGreaterOrEqual = (root: TreeNode, k: number): number => {
69 // Reset count to 0 to avoid influence from previous runs
70 count = 0;
71
72 // Perform a DFS starting from the root
73 dfs(root, k);
74
75 // Return the final count of nodes fulfilling the criteria
76 return count;
77};
78
Time and Space Complexity
Time Complexity:
The given Python code iterates through each element in the input list nums
with a for
loop. For each element v
, it enters a while
loop to square v
repeatedly until v
is no longer present in the set s
, incrementing t
each time a square is encountered in s
.
Let n
be the number of elements in nums
. The worst-case time complexity occurs when the squaring sequence for an element remains within the set s
for a prolonged series of operations. However, the squaring operation rapidly increases the value of v
, making it unlikely to have a long sequence unless the input values are specifically chosen to create a long chain (e.g., powers of 2). Nevertheless, in a pathological case, this repetition could occur O(m)
times for each element, where m
represents the maximum possible length of the squaring sequence within the set. However, m
could be considered constant in this context, as the numbers tend to grow very large very quickly and thus exit the set.
The in
operation within the while
loop has an average-case time complexity of O(1)
due to the set data structure.
Therefore, the total average-case time complexity is O(n)
, assuming m
doesn't depend on n
and is considered constant.
Space Complexity:
The space complexity of the code is dominated by the creation of the set s
, which contains unique elements from the list nums
. This set can have at most n
elements if all elements in nums
are unique.
Therefore, the space complexity is O(n)
.
Learn more about how to find time and space complexity quickly using problem constraints.
Which two pointer techniques do you use to check if a string is a palindrome?
Recommended Readings
Binary Search Speedrun For each of the Speedrun questions you will be given a binary search related problem and a corresponding multiple choice question The multiple choice questions are related to the techniques and template s introduced in the binary search section It's recommended that you have gone through at
What is Dynamic Programming Prerequisite DFS problems dfs_intro Backtracking problems backtracking Memoization problems memoization_intro Pruning problems backtracking_pruning Dynamic programming is an algorithmic optimization technique that breaks down a complicated problem into smaller overlapping sub problems in a recursive manner and uses solutions to the sub problems to construct a solution
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Got a question? Ask the Monster Assistant anything you don't understand.
Still not clear?  Submit the part you don't understand to our editors. Or join our Discord and ask the community.