Leetcode 2501: Longest Square Streak in an Array

In this Leetcode problem, we are given a list of ints, and we can rearrange them in any order we want to make a squares sequence such as [2,4,16].

The idea since we can rearrange the way we want is to first sort the array. That avoids the issue of encountering 16, and then 2, and then merge these 2 when we encounter 4, although it is something I considered doing. It is just simpler that way, as we know we are encountering all the integers in the sequence in order.

Once it is sorted, I used a Map to represent the sequences, the representation isn’t that intuitive, but I stored with the next square expected in the sequence as key. The reason I wanted this particular number to be a key is that when we go through the array, we want to know if a particular integer that we see is part of a sequence, so I just need to lookup by key, which is very fast. The value in the sequence representation is just the size of the sequence, since it is the size of the maximum subsequence that we want to return.

Simply translated into code:

class Solution {
    public int longestSquareStreak(int[] nums) {
        Map<Integer, Integer> nextSquareToLength = new HashMap<>();
        // First, sort nums so we don't have issues linking the squares together
        Arrays.sort(nums);
        int maxLength = 0;
        for (int num : nums) {
            if (nextSquareToLength.containsKey(num)) {
                int val = nextSquareToLength.get(num) + 1;
                nextSquareToLength.put(num*num, val);
                if (val > maxLength) {
                    maxLength = val;
                }
            } else {
                nextSquareToLength.put(num*num, 1);
            }
        }
        return (maxLength > 1) ? maxLength : -1;
    }
}