<p>You are given an integer array <code>nums</code>. A subsequence of <code>nums</code> is called a <strong>square streak</strong> if:</p>

<ul>
	<li>The length of the subsequence is at least <code>2</code>, and</li>
	<li><strong>after</strong> sorting the subsequence, each element (except the first element) is the <strong>square</strong> of the previous number.</li>
</ul>

<p>Return<em> the length of the <strong>longest square streak</strong> in </em><code>nums</code><em>, or return </em><code>-1</code><em> if there is no <strong>square streak</strong>.</em></p>

<p>A <strong>subsequence</strong> is an array that can be derived from another array by deleting some or no elements without changing the order of the remaining elements.</p>

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>

<pre>
<strong>Input:</strong> nums = [4,3,6,16,8,2]
<strong>Output:</strong> 3
<strong>Explanation:</strong> Choose the subsequence [4,16,2]. After sorting it, it becomes [2,4,16].
- 4 = 2 * 2.
- 16 = 4 * 4.
Therefore, [4,16,2] is a square streak.
It can be shown that every subsequence of length 4 is not a square streak.
</pre>

<p><strong class="example">Example 2:</strong></p>

<pre>
<strong>Input:</strong> nums = [2,3,5,6,7]
<strong>Output:</strong> -1
<strong>Explanation:</strong> There is no square streak in nums so return -1.
</pre>

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>2 &lt;= nums.length &lt;= 10<sup>5</sup></code></li>
	<li><code>2 &lt;= nums[i] &lt;= 10<sup>5</sup></code></li>
</ul>

class Solution:
    def longestSquareStreak(self, nums: List[int]) -> int:
        
        # elements are random, cannot know what came before or what can come
        # after. To get this information, one can think to sort the list. 
        # The thing is, there is a constant number of numbers to check:
        # if the number before n in the sequence exists (sqrt(n) and/or if
        # the number ahead of n in the streak exists (n**2)). If we can get
        # this information along with where they are , we can calc the streaks
        # length. We can do it as follows: first, go through the list to
        # get information on each unique number (duplicates mean nothing
        # to us, can pretend they don't exists). Store in a dict with the number
        # as the key. The value will be a 3-tuple with a the first value being
        # the index of the first seen instance number to prevent duplicate work 
        # since only the first instance will be used. .The second value will
        # be the index of
        # the next number in the streak if it exists, or None if it doesn't.
        # The second value in the tuple will be a boolean where True means 
        # the number that comes before it in the streak exists. Index not 
        # required since we will start at the bottom of the streak and "build"
        # the sequence from smallest to largest num. The boolean just tells us
        # if a specific number is the start of a sequence, the third value
        # in the tuple will be False, we can start building the streak from
        # there. If a number is NOT the start of the sequence, we will 
        # or have already built its streak from the first number, no
        # need to build here.

        # Iterate through list, put new numbers in dict and state their index
        info = dict()
        for i, num in enumerate(nums):
            if num in info:
                continue
            
            info[num] = [i, -1, -1]
        
        # Iterate through list again, now we know what numbers exists and where
        # so we can calculate if the previous number in the streak exists
        # and if the next one does.
        for i, num in enumerate(nums):
            # if this number exists somewhere else in the list, we will deal
            # with it in that other instance
            if info[num][0] != i:
                continue

            prev = sqrt(num)
            # if prev end in .0, it is an int so convert since only
            # ints are in nums
            if prev % 1 == 0:
                prev = int(prev)
            next_in_streak = num ** 2

            if next_in_streak in info:
                next_index = info[next_in_streak][0]
                info[num][1] = next_index

            if prev in info:
                prev_index = info[prev][0]
                info[num][2] = prev_index


        longest_streak = -1

        for i, num in enumerate(nums):
            if info[num][0] != i or info[num][2] != -1:
                continue
            curr_streak = 1
            current = num
            
            while info[current][1] != -1:
                next_index = info[current][1]
                current = nums[next_index]
                curr_streak += 1
            if curr_streak >= 2 and curr_streak > longest_streak:
                longest_streak = curr_streak


        print(info)
        return longest_streak
903