Array     C++     Depth-First Search     Hash Table     Java     Medium    

Problem Statement:

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:

  • nums.length == n
  • adjacentPairs.length == n - 1
  • adjacentPairs[i].length == 2
  • 2 <= n <= 105
  • -105 <= nums[i], ui, vi <= 105
  • There exists some nums that has adjacentPairs as its pairs.

Solution:

We can create an adjacency list by iterating over all adjacentPairs. This represents a graph with structure like an array ie two nodes (left and right ends) have one neighbor whereas the rest have two neighbors each. We can run DFS from one of the terminal nodes to get all nodes of graph in the order in which they appear in the original array.

 
class Solution {
    vector<int>res;
public:
    void dfs(unordered_map<int,vector<int>> &G, int cur, int par)
    {
        res.push_back(cur);
        for (int ch: G[cur])if(ch!=par) dfs(G,ch,cur);
    }
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) 
    {
        unordered_map<int,vector<int>> G;
        for(auto &v: adjacentPairs)
        {
            G[v[0]].push_back(v[1]);
            G[v[1]].push_back(v[0]);
        }
        int cur;
        for(auto &[k,v]:G)if(v.size()==1) {cur=k;break;}
        dfs(G,cur,-1);
        return res;
    }
};

SOLUTION II:

Since we already know the graph structure, we can also do the traversal in the following way:

We find out the start and end nodes. We initialize cur with start and iterate till cur is same as end.

 
class Solution {
public:
    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) 
    {
        unordered_map<int,vector<int>> G;
        for(auto &v: adjacentPairs)
        {
            G[v[0]].push_back(v[1]);
            G[v[1]].push_back(v[0]);
        }
        int start=-1,end=-1;
        for(auto &[k,v]:G)if(v.size()==1)if(start!=-1){end=k;break;}else start=k;
        int cur=start,prev=-1;
        vector<int> res {start};
        while(cur!=end)
        {
            for (int next: G[cur]) if(next==prev) continue; 
            else {prev=cur; cur=next; break;}
            res.push_back(cur);
        }
        return res;
    }
};

Java solution

 
class Solution {
    void dfs(Map<Integer, List<Integer>> H, int[]res, int cur, int index, int par)
    {
        res[index] = cur;
        for (int ch: H.get(cur)) if (ch==par) continue; else dfs(H,res,ch,index+1,cur);
    }
    public int[] restoreArray(int[][] adjacentPairs) 
    {
        Map<Integer, List<Integer>> H = new HashMap();
        for (int[] pair: adjacentPairs)
        {
            H.computeIfAbsent(pair[0], k->new ArrayList()).add(pair[1]);
            H.computeIfAbsent(pair[1], k->new ArrayList()).add(pair[0]);
        }
        int cur=-1;
        for(var entry: H.entrySet())if(entry.getValue().size()==1)
                                    {cur=entry.getKey();break;}
        int[] res = new int[adjacentPairs.length + 1];
        dfs(H,res,cur,0,-1);
        return res;
    }
}
 
 
class Solution {
    public int[] restoreArray(int[][] adjacentPairs) 
    {
        Map<Integer, List<Integer>> H = new HashMap();
        for (int[] pair: adjacentPairs)
        {
            H.computeIfAbsent(pair[0], k->new ArrayList()).add(pair[1]);
            H.computeIfAbsent(pair[1], k->new ArrayList()).add(pair[0]);
        }
        int start=-1, end=-1;
        for(var entry: H.entrySet())if(entry.getValue().size()==1)
        if(start!=-1){end=entry.getKey();break;} else start=entry.getKey();
        int[] res = new int[adjacentPairs.length + 1];
        res[0] = start;
        int cur = start, i=0, prev=-1;
        while(cur!=end)
        {
            for (int ch: H.get(cur)) if (ch==prev) continue;
            else {prev=cur; cur=ch; break;}
            res[++i] = cur;
        }
        return res;
    }
}