1743. Restore the Array From Adjacent Pairs

Difficulty:
Related Topics:
Similar Questions:

    Problem

    There is an integer array nums that consists of n **unique **elements, but you have forgotten it. However, you do remember every pair of adjacent elements in nums.

    You are given a 2D integer array adjacentPairs of size n - 1 where each adjacentPairs[i] = [ui, vi] indicates that the elements ui and vi are adjacent in nums.

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

    Return **the original array *nums*. If there are multiple solutions, return *any of them***.

      Example 1:

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

    Example 2:

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

    Example 3:

    Input: adjacentPairs = [[100000,-100000]]
    Output: [100000,-100000]
    

      Constraints:

    Solution

    /**
     * @param {number[][]} adjacentPairs
     * @return {number[]}
     */
    var restoreArray = function(adjacentPairs) {
        var map = {};
        for (var i = 0 ; i < adjacentPairs.length; i++) {
            map[adjacentPairs[i][0]] = map[adjacentPairs[i][0]] || [];
            map[adjacentPairs[i][1]] = map[adjacentPairs[i][1]] || [];
            map[adjacentPairs[i][0]].push(adjacentPairs[i][1]);
            map[adjacentPairs[i][1]].push(adjacentPairs[i][0]);
        }
        var root = Number(Object.keys(map).find(num => map[num].length === 1));
        var res = [root];
        var last = root;
        var now = map[root][0];
        while (now !== undefined) {
            var next = map[now][0] === last ? map[now][1] : map[now][0];
            res.push(now);
            last = now;
            now = next;
        }
        return res;
    };
    

    Explain:

    nope.

    Complexity: