Longest Square Streak in an Array

class Solution {
public:
    int maxSquareChain(vector<int>& arr) {
        unordered_map<int, int> squareMap;
    
        sort(arr.begin(), arr.end());
    
        for (int elem : arr) {
            int sqrRoot = (int)sqrt(elem);
    
            if (sqrRoot * sqrRoot == elem && squareMap.count(sqrRoot)) {
                squareMap[elem] = squareMap[sqrRoot] + 1;
            } else {
                squareMap[elem] = 1;
            }
        }
    
        int maxChain = 0;
        for (auto& [num, length] : squareMap) {
            maxChain = max(maxChain, length);
        }
    
        return maxChain == 1 ? -1 : maxChain;
    }
};

You aim to find the length of the longest chaining sequence of squares in an array with the provided code in C++. Iterate through multiple steps based on the given code to achieve the solution:

1. Implement the method maxSquareChain which takes a vector of integers arr as seen in the provided C++ code.

2. Create an unordered_map named squareMap to manage the count of each squared element and its chaining.

3. Sort the vector arr in ascending order.

4. Traverse through each element in the sorted array:

   • Calculate sqrRoot, the integer square root of the current element.
   • Verify if the squared value of sqrRoot equals the current element, and check if sqrRoot exists in squareMap.
   • If the previous conditions hold true, increment the chaining value for the current element based on its root's chain length.
   • Otherwise, initialize the chain length for this element to 1 within squareMap.

5. After setting up the map, initialize maxChain to 0, and iterate over squareMap to find the maximum value of chaining length.

6. Return the maximum chaining length if it is more than 1. Otherwise, return -1 to indicate no valid chaining sequence exists.

The method effectively utilizes a hashing strategy to link each square number with its square root predecessor forming a chain. This solution efficiently correlates elements, tracks chaining lengths, and determines the longest chaining sequence using the characteristics of square numbers.

class Solution {
    
    public int maxSquareSequence(int[] arr) {
        Map<Integer, Integer> lengthMap = new HashMap<>();
    
        Arrays.sort(arr);
    
        for (int num : arr) {
            int sqrt = (int) Math.sqrt(num);
    
            // Verify perfect square and check if exists in map
            if (sqrt * sqrt == num && lengthMap.containsKey(sqrt)) {
                // Extend existing square sequence
                lengthMap.put(num, lengthMap.get(sqrt) + 1);
            } else {
                // Initialize a new sequence
                lengthMap.put(num, 1);
            }
        }
    
        // Determining the maximum sequence length found
        int maxSequenceLength = 0;
        for (int value : lengthMap.values()) {
            maxSequenceLength = Math.max(maxSequenceLength, value);
        }
    
        // Returning adjusted value based on found sequences
        return maxSequenceLength == 1 ? -1 : maxSequenceLength;
    }
}

The Java code provided defines a method maxSquareSequence to find the longest streak of perfect square numbers in a sequence where each subsequent number is the square of its previous number. Here's the breakdown on how this code operates:

• The code initializes a HashMap to keep track of sequences of increasing square numbers.
• It sorts the array to ensure numbers are processed in ascending order.
• Iterating through the sorted array, it checks each number to determine if it's a perfect square. If it is, it also verifies if it continues a sequence from a previously encountered square number.
• For each perfect square, it either starts a new sequence or extends an existing one in the map.
• After processing all the numbers, the solution queries the map to find the length of the longest valid sequence.
• An adjustment is made at the end, where if the longest sequence is just one number, the method returns -1. Otherwise, it returns the length of the longest sequence found.

This method effectively utilizes hash mapping and array sorting to efficiently track and extend sequences of square numbers and determine the maximum sequence length.

class Solution:
    def findMaxSquaredSequence(self, arr: List[int]) -> int:
        # Keep record of sequences
        seq_record = {}
    
        arr.sort()
    
        for element in arr:
            square_root = int(element**0.5)
    
            # Update sequence if conditions are met
            if square_root * square_root == element and square_root in seq_record:
                seq_record[element] = seq_record[square_root] + 1
            else:
                seq_record[element] = 1
    
        # Determine maximum sequence length
        max_seq_len = max(seq_record.values(), default=0)
    
        # Return maximum length or -1
        return max_seq_len if max_seq_len > 1 else -1

The provided Python code implements a solution for determining the longest sequence of consecutive squared integers in an array. Follow these steps to understand the method:

1. Create a dictionary seq_record to keep track of sequences of squared integers.
2. Sort the array arr to ensure examination of elements in ascending order.
3. Iterate through each element in the sorted array:
   • Compute the integer square root of the element.
   • Verify if the element itself is a perfect square and if its square root is already recorded in seq_record. If so, update the sequence length by adding 1 to the value of its root in the dictionary.
   • If these conditions aren't met, start a new sequence with the current element and set its initial value to 1 in the dictionary.
4. Determine the maximum sequence length by finding the highest value in seq_record. Use the default=0 parameter with max() to handle cases where the dictionary might be empty.
5. Return the maximum sequence length if it is greater than 1; otherwise, return -1 to signify no valid sequence found.

This code effectively manages both the identification of perfect squares and the tracking of consecutive squared sequences, ensuring a clear assessment of the conditions where elements can form a sequenced streak. The use of sorting and dictionary operations ensures the algorithm handles unordered inputs and maintains an efficient lookup mechanism for extending sequences.