2501. Longest Square Streak in an Array

MediumArrayHash TableBinary SearchDynamic ProgrammingSorting
Leetcode Link

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 counter t to zero. This counter will be used to track the length of the square streak starting with v.

  • We then enter a while loop that continuously squares v and checks whether the new v is in the set s. If it is found, it means we can continue the square streak, and we increment the counter t 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 answer ans and update ans 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.

Not Sure What to Study? Take the 2-min Quiz to Find Your Missing Piece

Which type of traversal does breadth first search do?

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:

  1. Create a Set for Fast Lookups: The algorithm begins by converting the list nums into a set s. This transformation is done to take advantage of the constant time complexity O(1) for checking if an element is present in the set.

  2. Iterate Over the Array: For each element v in nums, we try to find the longest square streak starting with that number.

  3. Initialize a Counter: For each v, we set a counter t to zero. This counter will track the length of the streak.

  4. While Loop to Extend the Streak: We then enter a loop that continues as long as v is in the set s. Within this loop, we do two things:

    • Square v by setting v = 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.

  5. 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).

  6. Update Maximum Streak Length: If a valid streak is found, we compare t with the current maximum streak length ans, updating ans with max(ans, t) if necessary.

  7. 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.

Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:

What's the relationship between a tree and a graph?

Example 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:

  1. Create a Set for Fast Lookups: We convert nums into a set s for fast element lookup. So, s = {1, 16, 4, 2, 64}.

  2. Iterate Over the Array: We begin iterating with v = 1.

  3. Initialize a Counter: We set a temporary counter t = 0. This will track the length of a potential square streak.

  4. While Loop to Extend the Streak: We check if v = 1 is in s. It is, so we enter the loop.

    • We square v to get 1 * 1 = 1 and since 1 is still in the set s, we increment t 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 squared v is different from v.

    • Now, we should have v = 1, and t does not increase further as we are trapped in a loop where the value of v doesn't change.

    • To correct the algorithm and continue the example, we should stop incrementing t once we notice that v*v does not produce a new number.

  5. 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.

  6. Iterate Over the Next Array Element: v = 16

    • Initialize t = 0.
    • 16 is in s, square v to get 256. Since 256 is not in s, we stop the loop.
    • t remains 0 since 16 is not the beginning of a square streak within the set.

  7. Repeat the Process:

    • For v = 4, we initialize t = 0. Squaring v yields 16, which is in s. Increment t to 1. Squaring again yields 256, which is not in s, so we stop here. t is 1, so no valid streak.

    • With v = 2, square it to get 4, which is in s. Increment t to 1. Square 4 to get 16, which is in s. Increment t to 2. Square 16 to get 256, which is not in s, break. t is now 2, so we have found a valid streak of length 2. We set ans to 2 as it's the maximum so far.

    • For v = 64, we square it to get 4096, which is not in s, so the streak does not start here.

  8. Return the Result: After completing the iteration, the longest square streak found has a length of 2 (starting with v = 2), and hence we return ans = 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
Not Sure What to Study? Take the 2-min Quiz

Given a sorted array of integers and an integer called target, find the element that equals to the target and return its index. Select the correct code that fills the ___ in the given code snippet.

1def binary_search(arr, target):
2    left, right = 0, len(arr) - 1
3    while left ___ right:
4        mid = (left + right) // 2
5        if arr[mid] == target:
6            return mid
7        if arr[mid] < target:
8            ___ = mid + 1
9        else:
10            ___ = mid - 1
11    return -1
12
1public static int binarySearch(int[] arr, int target) {
2    int left = 0;
3    int right = arr.length - 1;
4
5    while (left ___ right) {
6        int mid = left + (right - left) / 2;
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16
1function binarySearch(arr, target) {
2    let left = 0;
3    let right = arr.length - 1;
4
5    while (left ___ right) {
6        let mid = left + Math.trunc((right - left) / 2);
7        if (arr[mid] == target) return mid;
8        if (arr[mid] < target) {
9            ___ = mid + 1;
10        } else {
11            ___ = mid - 1;
12        }
13    }
14    return -1;
15}
16

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.

Fast Track Your Learning with Our Quick Skills Quiz:

What are the two properties the problem needs to have for dynamic programming to be applicable? (Select 2)

Recommended Readings

Binary Search Speedrun

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

Dynamic Programming Introduction and Patterns

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

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 Teaching Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

←
↑TA đŸ‘šâ€đŸ«