Restore the Array From Adjacent Pairs

class Solution {
public:
    vector<int> reconstructArray(vector<vector<int>>& pairs) {
        unordered_map<int, vector<int>> adjacencyList;

        for (auto& pair : pairs) {
            adjacencyList[pair[0]].push_back(pair[1]);
            adjacencyList[pair[1]].push_back(pair[0]);
        }
        
        int startNode = 0;
        for (auto& item : adjacencyList) {
            if (item.second.size() == 1) {
                startNode = item.first;
                break;
            }
        }
        
        int current = startNode;
        vector<int> result = {startNode};
        int previous = INT_MAX;
        
        while (result.size() < adjacencyList.size()) {
            for (int next : adjacencyList[current]) {
                if (next != previous) {
                    result.push_back(next);
                    previous = current;
                    current = next;
                    break;
                }
            }
        }

        return result;
    }
};

To solve the problem of restoring an array from adjacent pairs using C++, follow this approach:

• Initialize adjacencyList as an unordered map to store the adjacency list of the array elements. Every element in the pairs vector points to its adjacent elements forming a connectivity graph.

• Populate the adjacencyList by iterating through each pair in the given pairs vector. Establish a two-way connection because each pair is bidirectional.

• Determine the starting node for the array reconstruction:

  • Traverse through adjacencyList to find an element with only one connection, which indicates one of the endpoints of the array.

• Start reconstructing the array from the determined start node:

  • Initialize current as the start node and add it to the result vector.
  • Use a variable previous to track the previously visited node to avoid moving backwards.

• Using a while loop, continue to reconstruct the array until the size of the result vector matches the size of the adjacency list:

  • Iterate over the adjacent nodes of the current node.
  • Check and ensure not to revisit the previous node.
  • Move to the next valid node, update the current and previous accordingly, then push the next node to the result vector.

• Return the reconstructed array contained within the result vector.

This approach effectively reconstructs the original array by utilizing the adjacency list representation to track and navigate through connected elements based on the provided pairs. The selection of the starting point as one of the ends ensures unidirectional array reconstruction.

class Solution {
    public int[] reconstructArray(int[][] pairs) {
        Map<Integer, List<Integer>> adjacencyMap = new HashMap<>();
        
        for (int[] pair : pairs) {
            int first = pair[0];
            int second = pair[1];

            if (!adjacencyMap.containsKey(first)) {
                adjacencyMap.put(first, new ArrayList<>());
            }
            
            if (!adjacencyMap.containsKey(second)) {
                adjacencyMap.put(second, new ArrayList<>());
            }
            
            adjacencyMap.get(first).add(second);
            adjacencyMap.get(second).add(first);
        }
        
        int startNode = 0;
        for (int key : adjacencyMap.keySet()) {
            if (adjacencyMap.get(key).size() == 1) {
                startNode = key;
                break;
            }
        }
        
        int currentNode = startNode;
        int[] result = new int[adjacencyMap.size()];
        result[0] = startNode;
        int index = 1;
        int previous = Integer.MAX_VALUE;
        
        while (index < adjacencyMap.size()) {
            for (int adj : adjacencyMap.get(currentNode)) {
                if (adj != previous) {
                    result[index] = adj;
                    index++;
                    previous = currentNode;
                    currentNode = adj;
                    break;
                }
            }
        }

        return result;
    }
}

The Java solution reconstructs an array from given adjacent pairs. This methodology revolves around using a HashMap to create an adjacency list from the pairs, determining the start node (which appears only once in the list), and then iterating through the map to construct the original array in order based on the adjacency connections.

• Step 1: Define a HashMap<Integer, List<Integer>> to store the adjacency list.
• Step 2: Loop through the provided pairs, adding each to the adjacency map to create an interconnected graph where each key links to its adjacent elements.
• Step 3: Identify the starting node of the array, which is an endpoint in the adjacency graph having only one connected node.
• Step 4: Initialize an array result with size equal to the adjacency map's key set size, to hold the reconstructed array.
• Step 5: Using a loop, fill the result array by navigating through the adjacency map starting from the identified initial node, ensuring correct array order following the original connections.
• Step 6: Return the reconstructed array which now holds the elements in their original configuration as per the adjacent pairs.

This use of an adjacency list coupled with a methodical traversal starting at an endpoint provides a robust way to reconstruct the original sequence from pair-wise connections, even if the initial order is unknown.

class Solution:
    def reconstructArray(self, pairs: List[List[int]]) -> List[int]:
        connections = defaultdict(list)
        
        for first, second in pairs:
            connections[first].append(second)
            connections[second].append(first)
        
        start = None
        for key in connections:
            if len(connections[key]) == 1:
                start = key
                break
        
        current = start
        result = [start]
        previous = None

        while len(result) < len(connections):
            for adj in connections[current]:
                if adj != previous:
                    result.append(adj)
                    previous = current
                    current = adj
                    break

        return result

The given Python code defines a Solution class with a method reconstructArray, designed to reconstruct an array from a list of adjacent pairs. The method uses Python’s defaultdict from the collections module to manage a graph-like structure where each node represents a number and edges connect pairs of adjacent numbers.

Here's a breakdown of the solution:

1. Initialize the graph where each number maps to its adjacent numbers:

   • Loop through each pair, updating the adjacency list for both numbers in the pair.

2. Determine the starting point of the array:

   • The starting point is identified as the number that appears only once in the adjacency list. This is true for the edges of the original sequence, which will only connect to one partner if they are the start or end of the array.

3. Reconstruct the array:

   • Start with the found start point, and initialize variables to hold the current number and the previous number to avoid loops.
   • Using a while loop, continue appending adjacent numbers. Every loop iteration selects the next number, ensuring it isn't the immediately previous number to avoid reversals until all numbers are placed into the result list.

4. The reconstructed array is returned after completion of the loop, containing all numbers in order based on the adjacency due to pairs.

This approach effectively restores the original sequence from a shuffled set of its adjacent pairs, leveraging graph traversal principles with careful handling of start and end edge cases in the structured sequence.