1743. Restore the Array From Adjacent Pairs

MediumArrayHash Table
Leetcode Link

Problem Description

In this problem, you have forgotten an integer array nums that consists of n unique elements. Despite not remembering the array itself, you do recall every pair of adjacent elements in nums. You are given a 2D integer array adjacentPairs with a size of n - 1. Each element adjacentPairs[i] = [u_i, v_i] indicates that the elements u_i and v_i are adjacent in the array nums.

It is guaranteed that every adjacent pair of elements nums[i] and nums[i+1] will be represented in adjacentPairs, either as [nums[i], nums[i+1]] or [nums[i+1], nums[i]]. These pairs can be listed in any order. Your task is to reconstruct and return the original array nums. If there are several possible arrays that fit the adjacent pairs, returning any one of them is acceptable.

Intuition

To restore the array, we need to recognize that the description constructs a path (like a one-dimensional graph) where each number except for the two endpoints has exactly two neighbors (think of nodes in a graph). The graph formed by adjacentPairs will have nodes with the following properties: the starting and ending elements (the ones found at the beginning and end of the array nums) will have only one adjacent element in adjacentPairs (they have a degree of one), while all other elements will have two adjacent elements (they have a degree of two). Identifying the unique starting or ending point allows us to sequentially rebuild the array from one end to the other.

The solution approach begins by creating a graph representation where each element of adjacentPairs is a node and the adjacent elements are the connected edges. Once the graph is built, we look for a node with a degree of one, which we know will be one of the endpoints in our original array. After identifying an endpoint, we can begin traversing the graph to 'visit' each node exactly once. The traversal is done by always moving to the 'unvisited' neighbor of the current node, adding each visited node to our answer array, ans. This process continues until the entire array is reconstructed, ensuring that all pairs are honored as they were in the original array.

Solution Approach

The Solution class in the provided Python code implements a function called restoreArray to solve the problem by reconstructing the original array from the given pairs of adjacent integers.

Here's a step-by-step walkthrough of the solution approach:

  1. Create a Graph Representation: To keep track of the adjacent nodes (the integers that can come before or after a given integer in the array), we use a defaultdict of lists, named g. A defaultdict is used here because it conveniently allows appending to lists for keys that have not been explicitly set. For each a, b pair in adjacentPairs, we add b as an adjacent node to a and vice versa.

    1g = defaultdict(list)
    2for a, b in adjacentPairs:
    3    g[a].append(b)
    4    g[b].append(a)
  2. Identify an Endpoint: Since we know the original array has unique elements with exactly two endpoints, we start by finding an integer that appears only once in the adjacency list (this has a graph degree of one) – meaning it's an endpoint.

    1for i, v in g.items():
    2    if len(v) == 1:
    3        ans[0] = i
    4        ans[1] = v[0]
    5        break
  3. Reconstruct the Array: Once we have one endpoint, we initialize our answer array ans with the starting endpoint as the first element. We also know what follows it immediately given our graph.

    From there, we traverse the graph to rebuild the original array. We iterate from the second to the last element of the ans array and at each step, pull the adjacent vertices from our graph. Since each element has two neighboring elements (except the endpoints), we can easily determine the next element in the array by checking which of the two vertices is not the one we've just visited (i.e., not the second-to-last element in ans).

    1n = len(adjacentPairs) + 1
    2ans = [0] * n
    3# ... previous endpoint identification code ...
    4for i in range(2, n):
    5    v = g[ans[i - 1]]
    6    ans[i] = v[0] if v[1] == ans[i - 2] else v[1]
  4. Return the Result: After the loop completes, ans contains the reconstructed array following the original order.

The nature of the problem aligns well with graph traversal algorithms – specifically, using a simple walk technique, as we are guaranteed a valid path that visits each node exactly once. The time complexity is O(N) because we visit each vertex exactly once, where N is the number of elements in the original array.

Ready to land your dream job?

Unlock your dream job with a 2-minute evaluator for a personalized learning plan!

Start Evaluator

Example Walkthrough

To illustrate the solution approach, let's take a small example. Suppose we have the following pairs of adjacent elements from the problem statement:

adjacentPairs = [[4,3], [1,2], [3,1]]

From these pairs, we need to reconstruct the original integer array nums. Here's how we would apply the solution approach:

  1. Create a Graph Representation: First, we create a graph by adding each pair to our adjacency list, representing each number and its corresponding adjacent numbers.

    We get the following graph:

    1{
    2  4: [3],
    3  3: [4, 1],
    4  1: [2, 3],
    5  2: [1]
    6}
  2. Identify an Endpoint: We look for an integer that appears only once in the adjacency list, as this will be an endpoint. In our graph, both 4 and 2 appear only once, so either can be chosen as the starting endpoint.

    Assume we pick 4 as the starting point. Our answer array ans tentatively starts with:

    1ans = [4, _]

    Since 4 is connected to 3, the next element is 3:

    1ans = [4, 3, _]
  3. Reconstruct the Array: From 3, we look at its neighbors, which are 4 (which we've just visited) and 1. So the next element is 1, and our array now looks like:

    1ans = [4, 3, 1, _]

    Continuing this, the next number we add is the neighbor of 1 which isn't 3 (since we've already been there). That's 2, resulting in:

    1ans = [4, 3, 1, 2]

    The array is now fully reconstructed.

  4. Return the Result: Finally, the reconstructed array ans = [4, 3, 1, 2] is the original array, considering the given adjacentPairs. Therefore, the result of the restoreArray function with the given input would be [4, 3, 1, 2].

In this example, the algorithm successfully reconstructs the original array from the pairs of adjacent elements. The use of graph representation simplifies the problem, making it more approachable and easier to solve efficiently.

Solution Implementation

1from collections import defaultdict
2
3class Solution:
4    def restoreArray(self, adjacentPairs):
5        # Create a graph using a dictionary where each key has an associated list of its adjacent nodes
6        graph = defaultdict(list)
7        for pair in adjacentPairs:
8            # Since it's an undirected graph, add each node to the list of its neighboring node
9            graph[pair[0]].append(pair[1])
10            graph[pair[1]].append(pair[0])
11
12        # The original array would have a length of one more than the number of adjacent pairs
13        array_length = len(adjacentPairs) + 1
14        restored_array = [0] * array_length
15
16        # Find the first and the second elements of the array, which are the endpoints of the path
17        # (having only one adjacent node)
18        for node, neighbors in graph.items():
19            if len(neighbors) == 1:  # Endpoints will only have one neighbor
20                restored_array[0] = node
21                restored_array[1] = neighbors[0]
22                break
23
24        # Construct the rest of the array
25        for i in range(2, array_length):
26            # Find the next adjacent node that is not the previous element in the array
27            current_neighbors = graph[restored_array[i - 1]]
28            # If the current node has only one neighbor, it must be the next element; otherwise 
29            # it is the one that is not the previously used element
30            restored_array[i] = current_neighbors[0] if current_neighbors[1] == restored_array[i - 2] else current_neighbors[1]
31
32        # Return the reconstructed array
33        return restored_array
34
1// Solution class to restore the array from its adjacent pairs
2class Solution {
3    // Method to restore array using adjacent pairs
4    public int[] restoreArray(int[][] adjacentPairs) {
5        // Calculate the total number of unique elements
6        int n = adjacentPairs.length + 1;
7        // Create a graph using a Map to store element and its adjacent elements
8        Map<Integer, List<Integer>> graph = new HashMap<>();
9      
10        // Iterate over each adjacent pair
11        for (int[] edge : adjacentPairs) {
12            // Unpack the pair
13            int a = edge[0], b = edge[1];
14            // Build the adjacency list for each element in the pair
15            graph.computeIfAbsent(a, k -> new ArrayList<>()).add(b);
16            graph.computeIfAbsent(b, k -> new ArrayList<>()).add(a);
17        }
18    
19        // Initialize the array to hold the restored sequence
20        int[] restoredArray = new int[n];
21      
22        // Find the first element (head of array) which will be an element with only one neighbor
23        for (Map.Entry<Integer, List<Integer>> entry : graph.entrySet()) {
24            if (entry.getValue().size() == 1) {
25                // Found the first element, which is the head of our restored array
26                restoredArray[0] = entry.getKey();
27                // The only neighbor is the second element
28                restoredArray[1] = entry.getValue().get(0);
29                break;
30            }
31        }
32      
33        // Reconstruct the array starting from index 2
34        for (int i = 2; i < n; ++i) {
35            // Get the neighbors of the last added element in restoredArray
36            List<Integer> neighbors = graph.get(restoredArray[i - 1]);
37            // Check the two neighbors to determine which is the next element in sequence
38            // If one neighbor is the same as the previous element in restoredArray, choose the other one
39            restoredArray[i] = neighbors.get(0) == restoredArray[i - 2] ? neighbors.get(1) : neighbors.get(0);
40        }
41      
42        // Return the restored array
43        return restoredArray;
44    }
45}
46
1#include <vector>
2#include <unordered_map>
3using namespace std;
4
5class Solution {
6public:
7    vector<int> restoreArray(vector<vector<int>>& adjacent_pairs) {
8        // Calculate the number of elements in the original array.
9        int num_elements = adjacent_pairs.size() + 1;
10      
11        // Create a graph represented as an adjacency list.
12        unordered_map<int, vector<int>> graph;
13        for (auto& edge : adjacent_pairs) {
14            int a = edge[0], b = edge[1];
15            graph[a].push_back(b);
16            graph[b].push_back(a);
17        }
18
19        // Initialize the answer array with the given size.
20        vector<int> answer(num_elements);
21      
22        // Find the starting element which is the one with only one neighbor.
23        for (auto& pair : graph) {
24            if (pair.second.size() == 1) {
25                answer[0] = pair.first;
26                answer[1] = pair.second[0];
27                break;
28            }
29        }
30
31        // Iterate over each element in the answer to find the next element.
32        for (int i = 2; i < num_elements; ++i) {
33            // Access the neighbors of the last added element.
34            auto neighbors = graph[answer[i - 1]];
35          
36            // The next element is the one which is not the previously added element.
37            answer[i] = neighbors[0] == answer[i - 2] ? neighbors[1] : neighbors[0];
38        }
39
40        // Return the restored original array.
41        return answer;
42    }
43};
44
1type AdjacencyList = Map<number, number[]>;
2
3// Restore the array from the given adjacency pairs
4function restoreArray(adjacentPairs: number[][]): number[] {
5  // Calculate the number of elements in the original array
6  const numElements: number = adjacentPairs.length + 1;
7
8  // Create a graph represented as an adjacency list
9  const graph: AdjacencyList = new Map<number, number[]>();
10  for (const [a, b] of adjacentPairs) {
11    if (!graph.has(a)) graph.set(a, []);
12    if (!graph.has(b)) graph.set(b, []);
13    graph.get(a)!.push(b);
14    graph.get(b)!.push(a);
15  }
16
17  // Initialize the answer array with the given size
18  const answer: number[] = new Array(numElements);
19
20  // Find the starting element which is the one with only one neighbor
21  for (const [key, neighbors] of graph) {
22    if (neighbors.length === 1) {
23      answer[0] = key;
24      answer[1] = neighbors[0];
25      break;
26    }
27  }
28
29  // Iterate over each element in the answer to find the next element
30  for (let i = 2; i < numElements; ++i) {
31    // Access the neighbors of the last added element
32    const neighbors = graph.get(answer[i - 1])!;
33  
34    // The next element is the one which is not the previously added element
35    answer[i] = neighbors[0] === answer[i - 2] ? neighbors[1] : neighbors[0];
36  }
37
38  // Return the restored original array
39  return answer;
40}
41
42// Example usage:
43const adjacentPairs = [[2, 1], [3, 4], [3, 2]];
44const restoredArray = restoreArray(adjacentPairs);
45console.log(restoredArray);  // Output will be the restored array based on the given adjacent pairs
46

Time and Space Complexity

Time Complexity

The time complexity of the given code can be analyzed as follows:

  • Building the graph g has a complexity of O(m), where m is the number of adjacent pairs. Every adjacent pair requires two insert operations in the dictionary.

  • Finding the starting node (where the degree is 1) has a maximum complexity of O(n) where n is the number of unique nodes. This is because in the worst case, we have to check every entry in the dictionary.

  • Reconstructing the array ans requires us to iterate n - 2 times (since the first two elements are already filled), and in each iteration, we find the next node in O(1) time (since we're dealing with at most two elements in a list, and we know one of them is the previous node). So, the complexity for this part is O(n).

Overall, the time complexity is O(m + n + n) => O(m + 2n). Since m = n - 1, we simplify the time complexity to O(n).

Space Complexity

The space complexity of the given code can be analyzed as follows:

  • The graph g will contain each unique node and its adjacent nodes. Since each edge contributes to two nodes' adjacency lists, the space needed for g is O(2m).

  • The ans array will contain n elements, so it requires O(n) space.

Together, the space complexity for storing the graph and the array amounts to O(2m + n). Since m = n - 1, we can simplify the space complexity to O(n).

Hence, both time and space complexities of the given code are O(n).

Learn more about how to find time and space complexity quickly using problem constraints.


Discover Your Strengths and Weaknesses: Take Our 2-Minute Quiz to Tailor Your Study Plan:
Question 1 out of 10

Which algorithm should you use to find a node that is close to the root of the tree?


Recommended Readings

Got a question? Ask the Monster Assistant anything you don't understand.

Still not clear? Ask in the Forum,  Discord or Submit the part you don't understand to our editors.

Coding Interview Strategies

Dive into our free, detailed pattern charts and company guides to understand what each company focuses on.

See Patterns

🪄