1743. Restore the Array From Adjacent Pairs

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.

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

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.