<p>There is an integer array <code>nums</code> that consists of <code>n</code> <strong>unique </strong>elements, but you have forgotten it. However, you do remember every pair of adjacent elements in <code>nums</code>.</p>

<p>You are given a 2D integer array <code>adjacentPairs</code> of size <code>n - 1</code> where each <code>adjacentPairs[i] = [u<sub>i</sub>, v<sub>i</sub>]</code> indicates that the elements <code>u<sub>i</sub></code> and <code>v<sub>i</sub></code> are adjacent in <code>nums</code>.</p>

<p>It is guaranteed that every adjacent pair of elements <code>nums[i]</code> and <code>nums[i+1]</code> will exist in <code>adjacentPairs</code>, either as <code>[nums[i], nums[i+1]]</code> or <code>[nums[i+1], nums[i]]</code>. The pairs can appear <strong>in any order</strong>.</p>

<p>Return <em>the original array </em><code>nums</code><em>. If there are multiple solutions, return <strong>any of them</strong></em>.</p>

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

<pre>
<strong>Input:</strong> adjacentPairs = [[2,1],[3,4],[3,2]]
<strong>Output:</strong> [1,2,3,4]
<strong>Explanation:</strong> This array has all its adjacent pairs in adjacentPairs.
Notice that adjacentPairs[i] may not be in left-to-right order.
</pre>

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

<pre>
<strong>Input:</strong> adjacentPairs = [[4,-2],[1,4],[-3,1]]
<strong>Output:</strong> [-2,4,1,-3]
<strong>Explanation:</strong> There can be negative numbers.
Another solution is [-3,1,4,-2], which would also be accepted.
</pre>

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

<pre>
<strong>Input:</strong> adjacentPairs = [[100000,-100000]]
<strong>Output:</strong> [100000,-100000]
</pre>

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

<ul>
	<li><code>nums.length == n</code></li>
	<li><code>adjacentPairs.length == n - 1</code></li>
	<li><code>adjacentPairs[i].length == 2</code></li>
	<li><code>2 &lt;= n &lt;= 10<sup>5</sup></code></li>
	<li><code>-10<sup>5</sup> &lt;= nums[i], u<sub>i</sub>, v<sub>i</sub> &lt;= 10<sup>5</sup></code></li>
	<li>There exists some <code>nums</code> that has <code>adjacentPairs</code> as its pairs.</li>
</ul>

class Solution:
    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
        '''
        num array of n unique elemtns

        list of adjacent parirs: 
            - u, v 
            - means either order u, v
                - or order       v, u
        
        - build the original array nums while the pairs appear in any order
        - note that the numbers in the array are unique
        - so each adjacent pair u, v refers to a specific key or location 
        in original array

        the paird appear in any order

        brute force approach: 
            - try every single combination of unique integers given 
                - and check if they meet the conditions 
                - terrible runtime
            
    

            - put the adjacent pairs stuff into a hashmap so we can easily access 
                - who is next to who
                - there should not be any that are 3 or more
            
            - realize that either the head or the tail has 1 adjacent only 
            - start from there and build the string form there
        
        hashmap of #key into set
                #inte --> set of adj ints
                #use the start as one of TWWO (happy case, 1 if single length array)
                    #build the array from ther
                    #1 -> adj = 2 
                        #when we choose 2, we remove 1 from 2's list
        '''
        adj = {}
        for u, v in adjacentPairs:
            if u not in adj: 
                adj[u] = []
            if v not in adj: 
                adj[v] = []
            
            adj[u].append(v)
            adj[v].append(u)

        start = None
        for key in adj.keys():
            if len(adj[key]) == 1: 
                start = key
                break
        
       
        prev = None
        curr = start
        res = [curr]
        N = len(adj)
        while len(res) < N: 
            for nei in adj[curr]: 
                if nei != prev: 
                    res.append(nei)
                    prev = curr
                    curr = nei
                    break
            #then select the the next element in the list from the remaining adj in curr
            #this line removes next element from the adj list of "prev"
        
        return res



        
        
64025