Restore the Array from Adjacent Pairs (LeetCode)

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:

• 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

   public int[] RestoreArray(int[][] adjacentPairs) {
        var numArray = new List<int[]>();
        var adjacentDic = new Dictionary<int, int?[]>(); // stores adjancets of each number
        var adjacentDicValuElCount = new Dictionary<int, int>();

        int?[] currentArray = null;
        var indexOfInsertion = -1;

        for (int i = 0; i < adjacentPairs.Length; i++) {
            // try get the array reference for the first element of current pair
            adjacentDic.TryGetValue(adjacentPairs[i][0], out currentArray);
            if (currentArray != null) {
                adjacentDicValuElCount.TryGetValue(adjacentPairs[i][0], out indexOfInsertion);
                currentArray[indexOfInsertion + 1] = adjacentPairs[i][1];
            } else {
                // create the entry in the adjacent and index tracking dictionaries
                adjacentDic.Add(adjacentPairs[i][0], new int?[3]{adjacentPairs[i][1] ,null, null});
                adjacentDicValuElCount.Add(adjacentPairs[i][0], 0);
            }

            // do the same for second element of current pair
            adjacentDic.TryGetValue(adjacentPairs[i][1], out currentArray);

            if (currentArray != null) {
                adjacentDicValuElCount.TryGetValue(adjacentPairs[i][1], out indexOfInsertion);
                currentArray[indexOfInsertion + 1] = adjacentPairs[i][0];
            } else {
                // create the entry in the adjacent and index tracking dictionaries
                adjacentDic.Add(adjacentPairs[i][1], new int?[3]{adjacentPairs[i][0] ,null, null});
                adjacentDicValuElCount.Add(adjacentPairs[i][1], 0);
            }
        }

        // now the starting and end element will be those which have only one adjacent.
        var outputArray = new int[adjacentPairs.Length + 1];
        var startPairIndex = 0; // Which pair is the starting point
        var flipStart = false;
        int outputArrayIndex = -1; // output array index till where we have sequence
	    int?[] currentValue = null;

	   // find the starting pair
	   // The item which have one element as it's neighbour is the starting or end.
	   // So we have to loop max 4 times. (Icluding Flip)
	   var possibleStarts = adjacentDic.Where(i => i.Value.Where(v => v.HasValue).Count() == 1);
	   var possibleStartPairs = new int[][]{new int[] {possibleStarts.ElementAt(0).Key, (int)possibleStarts.ElementAt(0).Value[0]}, 
											new int[] {possibleStarts.ElementAt(1).Key, (int)possibleStarts.ElementAt(1).Value[0]}, 
										   };
	   
        while(outputArrayIndex != adjacentPairs.Length && startPairIndex < possibleStartPairs.Length) {
            if (outputArrayIndex == -1) {
                    if (!flipStart) {
                        outputArray[0] = possibleStartPairs[startPairIndex][0];
                        outputArray[1] = possibleStartPairs[startPairIndex][1];
                        outputArrayIndex+=2;
                    } else {
                        outputArray[0] = possibleStartPairs[startPairIndex][1];
                        outputArray[1] = possibleStartPairs[startPairIndex][0];
                        outputArrayIndex+=2;
                    }
                }
            else {
                // find next element for current last value in outputArray
                adjacentDic.TryGetValue(outputArray[outputArrayIndex], out currentValue);
                var nextValue = Array.Find(currentValue, v => v != outputArray[outputArrayIndex - 1]);
                if (nextValue != null) {
                    // save the next value to array
                    outputArrayIndex++;
                    outputArray[outputArrayIndex] = (int)nextValue;
                } else {
                    // restart the 'nums' finding
                    // if already flipped make next pair as start.
                    if (flipStart) {
                        startPairIndex++;
                        flipStart = false;
                    }
                    // flip the start
                    else {
                        flipStart = true;
                    }
                    outputArrayIndex = -1;
                }
            }
        }
        return outputArray;
    }