Restore the Array From Adjacent Pairs

Med

#1596Time: O(N^2), where N is the number of elements in the array. The outer loop runs N-1 times, and inside it, we iterate through the `adjacentPairs` array of size N-1. This results in a quadratic runtime.Space: O(N), where N is the number of elements in the array. This space is used to store the frequency counts of numbers and the result array.1 company

Algorithms

Depth-First Search

Data structures

Array Hash Table

Companies

Robinhood

Prompt

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] = [u_i, v_i] indicates that the elements u_i and v_i 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 <= 10⁵
-10⁵ <= nums[i], u_i, v_i <= 10⁵
There exists some nums that has adjacentPairs as its pairs.

Approaches

2 approaches with complexity analysis and trade-offs.

This approach reconstructs the array by repeatedly scanning the input adjacentPairs to find the next element in the sequence. It starts by identifying an endpoint and then iteratively builds the array element by element without building an explicit graph.

Algorithm

Create a map to count the occurrences of each number in adjacentPairs.
Find a number that appears only once. This will be one of the endpoints of the array.
Initialize the result array ans with this starting endpoint.
Set a prev variable to a sentinel value (one that cannot be in the input) and curr to the starting endpoint.
Loop n-1 times to find the rest of the elements:
- In each iteration, scan the entire adjacentPairs array.
- Find a pair [u, v] where one element equals curr and the other does not equal prev.
- The element that is not prev is the next element in the sequence.
- Add this next element to the ans array.
- Update prev to curr and curr to the newly added element.
Return the ans array.

Walkthrough

This method reconstructs the array by iteratively finding the next adjacent element. It avoids building an explicit graph structure but pays a price in performance.

The algorithm proceeds as follows:

First, we need a starting point. The endpoints of the original array are unique in that they only have one neighbor, while all other elements have two. We can find an endpoint by counting the frequency of each number in the adjacentPairs. A number appearing only once must be an endpoint.
We initialize our result array with this starting number.
We then loop n-1 times to find the remaining elements. In each iteration, we search through the adjacentPairs list to find a pair that contains the last element added to our result (curr).
To ensure we move forward along the path, we keep track of the prev element and pick the neighbor of curr that is not prev.
Once we find the next element, we append it to our result and continue the process until the array is fully reconstructed.

This repeated scanning of the adjacentPairs list in each step leads to a quadratic time complexity.

1import java.util.*;2 3class Solution {4    public int[] restoreArray(int[][] adjacentPairs) {5        int n = adjacentPairs.length + 1;6        Map<Integer, Integer> counts = new HashMap<>();7        for (int[] pair : adjacentPairs) {8            counts.put(pair[0], counts.getOrDefault(pair[0], 0) + 1);9            counts.put(pair[1], counts.getOrDefault(pair[1], 0) + 1);10        }11 12        int startNode = -1;13        for (Map.Entry<Integer, Integer> entry : counts.entrySet()) {14            if (entry.getValue() == 1) {15                startNode = entry.getKey();16                break;17            }18        }19 20        int[] result = new int[n];21        result[0] = startNode;22        int curr = startNode;23        int prev = Integer.MIN_VALUE; // A value guaranteed not to be in the array24 25        for (int i = 1; i < n; i++) {26            // Search for the next element by scanning all pairs27            for (int[] pair : adjacentPairs) {28                if (pair[0] == curr && pair[1] != prev) {29                    result[i] = pair[1];30                    break;31                } else if (pair[1] == curr && pair[0] != prev) {32                    result[i] = pair[0];33                    break;34                }35            }36            prev = curr;37            curr = result[i];38        }39        return result;40    }41}

Complexity

Time

O(N^2), where N is the number of elements in the array. The outer loop runs N-1 times, and inside it, we iterate through the `adjacentPairs` array of size N-1. This results in a quadratic runtime.

Space

O(N), where N is the number of elements in the array. This space is used to store the frequency counts of numbers and the result array.

Trade-offs

Pros

Conceptually straightforward without needing explicit graph data structures.
Relatively easy to implement for those less familiar with graphs.

Cons

Highly inefficient due to the nested loop structure, where the entire adjacentPairs list is scanned for each element of the output array.
Will result in a 'Time Limit Exceeded' error on platforms like LeetCode for larger test cases.

This optimal approach models the problem as finding a path in a graph. The numbers are treated as nodes and the adjacent pairs as edges. By building an adjacency list using a hash map, we can easily find an endpoint (a node with only one edge) and then traverse the graph in linear time to reconstruct the original array.

Algorithm

Create a HashMap<Integer, List<Integer>> to serve as an adjacency list for the graph.
Iterate through adjacentPairs. For each pair [u, v], add v to u's neighbor list and u to v's neighbor list.
Find the starting node for the traversal. Iterate through the HashMap to find a key whose value (list of neighbors) has a size of 1. This node is an endpoint of the original array.
Initialize the result array ans of size N.
Start a traversal from the identified endpoint. Use a prev variable to keep track of the previously visited node to avoid going backward.
In a loop for N iterations, add the curr node to ans, find its unvisited neighbor (the one not equal to prev), and update prev and curr.
Return the ans array.

Walkthrough

The most efficient way to solve this problem is to view it as a graph problem. Each number is a node, and an adjacent pair [u, v] represents an edge connecting nodes u and v. Since the original array was a simple sequence of unique numbers, the resulting graph is a simple path.

The core idea is to:

Build the Graph: Construct an adjacency list representation of the graph using a HashMap. The keys will be the numbers (nodes), and the values will be lists of their neighbors. We iterate through adjacentPairs, and for each pair [u, v], we add v to u's adjacency list and u to v's list.
Find an Endpoint: In a path graph, the two endpoints have a degree of 1 (only one neighbor), while all intermediate nodes have a degree of 2. We can find a starting point for our traversal by iterating through our map and finding any node whose adjacency list has a size of 1.
Traverse the Path (DFS): Starting from the endpoint, we perform a traversal to reconstruct the array. We build the result array one element at a time. At each step, we look at the neighbors of the current node. Since we are traversing a path, there will be only one unvisited neighbor (the one not equal to the previous node). We move to that neighbor, add it to our result, and repeat until all n elements are found.

This approach processes each pair and each number a constant number of times, resulting in a linear time complexity.

1import java.util.*;2 3class Solution {4    public int[] restoreArray(int[][] adjacentPairs) {5        Map<Integer, List<Integer>> graph = new HashMap<>();6 7        // 1. Build the graph8        for (int[] pair : adjacentPairs) {9            graph.computeIfAbsent(pair[0], k -> new ArrayList<>()).add(pair[1]);10            graph.computeIfAbsent(pair[1], k -> new ArrayList<>()).add(pair[0]);11        }12 13        // 2. Find the starting node (an endpoint with degree 1)14        int startNode = -1;15        for (Map.Entry<Integer, List<Integer>> entry : graph.entrySet()) {16            if (entry.getValue().size() == 1) {17                startNode = entry.getKey();18                break;19            }20        }21 22        // 3. Traverse the path to reconstruct the array23        int n = adjacentPairs.length + 1;24        int[] result = new int[n];25        int curr = startNode;26        int prev = Integer.MIN_VALUE; // Sentinel value27 28        for (int i = 0; i < n; i++) {29            result[i] = curr;30            List<Integer> neighbors = graph.get(curr);31            32            // Find the next node in the path33            // For the last node, neighbors will be just prev, loop won't run, curr won't be updated, which is fine.34            for (int neighbor : neighbors) {35                if (neighbor != prev) {36                    prev = curr;37                    curr = neighbor;38                    break;39                }40            }41        }42 43        return result;44    }45}

Complexity

Time

O(N), where N is the number of elements. Building the graph takes O(N) time as we process N-1 pairs. Finding the start node takes O(N) in the worst case. The final traversal visits each node and edge once, which is also O(N).

Space

O(N), where N is the number of elements. This space is required to store the graph's adjacency list in the `HashMap` and the result array. The map will store N nodes and 2*(N-1) total neighbor entries.

Trade-offs

Pros

Highly efficient with linear time complexity.
Scales well for large inputs, which is crucial given the constraints (N up to 10^5).
It's a standard and robust technique for path-related problems.

Cons

Requires familiarity with graph representations like adjacency lists.
Slightly more complex to implement than the naive approach due to the setup of the graph data structure.

Solutions

Solution

1public class Solution { public int [] RestoreArray ( int [][] adjacentPairs ) { int n = adjacentPairs . Length + 1 ; Dictionary < int , List < int >> g = new Dictionary < int , List < int >>(); foreach ( int [] e in adjacentPairs ) { int a = e [ 0 ], b = e [ 1 ]; if (! g . ContainsKey ( a )) { g [ a ] = new List < int >(); } if (! g . ContainsKey ( b )) { g [ b ] = new List < int >(); } g [ a ]. Add ( b ); g [ b ]. Add ( a ); } int [] ans = new int [ n ]; foreach ( var entry in g ) { if ( entry . Value . Count == 1 ) { ans [ 0 ] = entry . Key ; ans [ 1 ] = entry . Value [ 0 ]; break ; } } for ( int i = 2 ; i < n ; ++ i ) { List < int > v = g [ ans [ i - 1 ]]; ans [ i ] = v [ 1 ] == ans [ i - 2 ] ? v [ 0 ] : v [ 1 ]; } return ans ; } }

1class Solution { public int [] restoreArray ( int [][] adjacentPairs ) { int n = adjacentPairs . length + 1 ; Map < Integer , List < Integer >> g = new HashMap <>(); for ( int [] e : adjacentPairs ) { int a = e [ 0 ], b = e [ 1 ]; g . computeIfAbsent ( a , k -> new ArrayList <>()). add ( b ); g . computeIfAbsent ( b , k -> new ArrayList <>()). add ( a ); } int [] ans = new int [ n ]; for ( Map . Entry < Integer , List < Integer >> entry : g . entrySet ()) { if ( entry . getValue (). size () == 1 ) { ans [ 0 ] = entry . getKey (); ans [ 1 ] = entry . getValue (). get ( 0 ); break ; } } for ( int i = 2 ; i < n ; ++ i ) { List < Integer > v = g . get ( ans [ i - 1 ]); ans [ i ] = v . get ( 1 ) == ans [ i - 2 ] ? v . get ( 0 ) : v . get ( 1 ); } return ans ; } }

1class Solution { public: vector < int > restoreArray ( vector < vector < int >>& adjacentPairs ) { int n = adjacentPairs . size () + 1 ; unordered_map < int , vector < int >> g ; for ( auto & e : adjacentPairs ) { int a = e [ 0 ], b = e [ 1 ]; g [ a ]. push_back ( b ); g [ b ]. push_back ( a ); } vector < int > ans ( n ); for ( auto & [ k , v ] : g ) { if ( v . size () == 1 ) { ans [ 0 ] = k ; ans [ 1 ] = v [ 0 ]; break ; } } for ( int i = 2 ; i < n ; ++ i ) { auto v = g [ ans [ i - 1 ]]; ans [ i ] = v [ 0 ] == ans [ i - 2 ] ? v [ 1 ] : v [ 0 ]; } return ans ; } };

1class Solution : def restoreArray ( self , adjacentPairs : List [ List [ int ]]) -> List [ int ]: g = defaultdict ( list ) for a , b in adjacentPairs : g [ a ]. append ( b ) g [ b ]. append ( a ) n = len ( adjacentPairs ) + 1 ans = [ 0 ] * n for i , v in g . items (): if len ( v ) == 1 : ans [ 0 ] = i ans [ 1 ] = v [ 0 ] break for i in range ( 2 , n ): v = g [ ans [ i - 1 ]] ans [ i ] = v [ 0 ] if v [ 1 ] == ans [ i - 2 ] else v [ 1 ] return ans

Video walkthrough

Newsletter

One sharp idea, every week

System design and interview prep — short enough to finish.

No spam. Unsubscribe anytime.

Practice

Same difficulty — related problems to reinforce the pattern.

← Previous

Previous problem

Next problem