Graph in disguise

Take a look at this problem: Restore the Array From Adjacent Pairs - LeetCode

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.

Accepted

6,461

Submissions

10,423

This is simply a graph in disguise problem. Find one of the extremities of the array (I call it "root", but that's technically not right). From there, perform a DFS in the graph looking for a path from one extremity of the graph to the other one. The DFS might take some time, it is not the most efficient way, but should do the trick. Notice that my graph is implemented using just one Hashtable. Code is down below, cheers, ACC.

public int[] RestoreArray(int[][] adjacentPairs)
{
    Hashtable uniqueElements = new Hashtable();
    Hashtable roots = new Hashtable();
    Hashtable graph = new Hashtable();

    for (int i = 0; i < adjacentPairs.Length; i++)
    {
        int a = adjacentPairs[i][0];
        int b = adjacentPairs[i][1];

        if (!uniqueElements.ContainsKey(a)) uniqueElements.Add(a, false);
        if (!uniqueElements.ContainsKey(b)) uniqueElements.Add(b, false);

        if (roots.ContainsKey(a)) roots.Remove(a);
        else roots.Add(a, true);
        if (roots.ContainsKey(b)) roots.Remove(b);
        else roots.Add(b, true);

        if (!graph.ContainsKey(a)) graph.Add(a, new Hashtable());
        Hashtable at = (Hashtable)graph[a];
        if (!at.ContainsKey(b)) at.Add(b, true);
        if (!graph.ContainsKey(b)) graph.Add(b, new Hashtable());
        Hashtable bt = (Hashtable)graph[b];
        if (!bt.ContainsKey(a)) bt.Add(a, true);
    }

    int root = -1;
    foreach (int key in roots.Keys)
    {
        root = key;
        break;
    }

    List retVal = new List();
    retVal.Add(root);
    uniqueElements[root] = true;
    if (TraverseGraph(root, uniqueElements, graph, ref retVal))
    {
        return retVal.ToArray();
    }
    return null;
}

private bool TraverseGraph(int currentElement,
                            Hashtable visited,
                            Hashtable graph,
                            ref List output)
{
    if (output.Count == visited.Count) return true;

    Hashtable neighbors = (Hashtable)graph[currentElement];

    foreach (int n in neighbors.Keys)
    {
        if (!(bool)visited[n])
        {
            output.Add(n);
            visited[n] = true;
            if (TraverseGraph(n, visited, graph, ref output)) return true;
            visited[n] = false;
            output.RemoveAt(output.Count - 1);
        }
    }

    return false;
}