Leetcode 1743. Restore the Array From Adjacent Pairs

Problem Explanation

The problem is about restoring an original integer array, given pairs of its adjacent elements. More specifically, we are given a 2D integer array adjacentPairs, where each element of this array is a pair of adjacent elements from the original array. The order of these pairs in the 2D array may not be the order in which they originally appeared in the original array. We need to find the original array using the given adjacent pairs.

Let's walk through an example to understand the problem more clearly.

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

Here, we have three adjacent pairs: (2,1), (3,4), and (3,2). We can see that the correct original array is [1,2,3,4] because all given pairs are adjacent in this array.

Approach

To solve this problem, we will use a hash map to store each element of the given array and its adjacent elements. Then we will find an element that has only one adjacent element (it will be the starting or ending element of the original array) and start building the original array using the hash map.

The main idea is to traverse through the given adjacent pairs, and for each pair, update the hash map by adding the adjacent element for each element of the pair.

Let's understand this approach with an example:

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

1. Initialize an empty hash map numToAdjs

2. Traverse through the given adjacent pairs

   a. For the pair (2,1), add 1 as an adjacent element of 2 and 2 as an adjacent element of 1 in the hash map

   1numToAdjs = {1: [2], 2: [1]}

   b. For the pair (3,4), add 4 as an adjacent element of 3 and 3 as an adjacent element of 4 in the hash map

   1numToAdjs = {1: [2], 2: [1], 3:[4], 4:[3]}

   c. For the pair (3,2), add 2 as an adjacent element of 3 and 3 as an adjacent element of 2 in the hash map

   1numToAdjs = {1: [2], 2: [1, 3], 3: [4, 2], 4: [3]}

3. Find the starting element of the original array (an element that has only one adjacent element) and start building the original array using the hash map

   a. Element 1 has only one adjacent element (2), so the starting element is 1

   b. Build the original array

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

4. Return the original array

Solution in Python

1from collections import defaultdict
2
3class Solution:
4    def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]:
5        numToAdjs = defaultdict(list)
6        
7        for pair in adjacentPairs:
8            u, v = pair
9            numToAdjs[u].append(v)
10            numToAdjs[v].append(u)
11        
12        ans = []
13        for num, adjs in numToAdjs.items():
14            if len(adjs) == 1:
15                ans.append(num)
16                ans.append(adjs[0])
17                break
18                
19        while len(ans) < len(adjacentPairs) + 1:
20            tail = ans[-1]
21            prev = ans[-2]
22            adjs = numToAdjs[tail]
23            if adjs[0] == prev:
24                ans.append(adjs[1])
25            else:
26                ans.append(adjs[0])
27                
28        return ans

Solution in Java

1import java.util.ArrayList;
2import java.util.HashMap;
3import java.util.List;
4import java.util.Map;
5
6class Solution {
7    public int[] restoreArray(int[][] adjacentPairs) {
8        Map<Integer, List<Integer>> numToAdjs = new HashMap<>();
9        
10        for (int[] pair : adjacentPairs) {
11            int u = pair[0];
12            int v = pair[1];
13            numToAdjs.putIfAbsent(u, new ArrayList<>());
14            numToAdjs.putIfAbsent(v, new ArrayList<>());
15            numToAdjs.get(u).add(v);
16            numToAdjs.get(v).add(u);
17        }
18        
19        int[] ans = new int[adjacentPairs.length + 1];
20        for (int num : numToAdjs.keySet()) {
21            if (numToAdjs.get(num).size() == 1) {
22                ans[0] = num;
23                ans[1] = numToAdjs.get(num).get(0);
24                break;
25            }
26        }
27        
28        for (int i = 2; i < ans.length; i++) {
29            int tail = ans[i - 1];
30            int prev = ans[i - 2];
31            List<Integer> adjs = numToAdjs.get(tail);
32            if (adjs.get(0) == prev) {
33                ans[i] = adjs.get(1);
34            } else {
35                ans[i] = adjs.get(0);
36            }
37        }
38        
39        return ans;
40    }
41}

Solution in JavaScript

1class Solution {
2    restoreArray(adjacentPairs) {
3        let numToAdjs = new Map();
4        
5        for (let pair of adjacentPairs) {
6            let u = pair[0];
7            let v = pair[1];
8            if (!numToAdjs.has(u)) numToAdjs.set(u, []);
9            if (!numToAdjs.has(v)) numToAdjs.set(v, []);
10            numToAdjs.get(u).push(v);
11            numToAdjs.get(v).push(u);
12        }
13        
14        let ans = [];
15        for (let [num, adjs] of numToAdjs.entries()) {
16            if (adjs.length === 1) {
17                ans.push(num);
18                ans.push(adjs[0]);
19                break;
20            }
21        }
22        
23        while (ans.length < adjacentPairs.length + 1) {
24            let tail = ans[ans.length - 1];
25            let prev = ans[ans.length - 2];
26            let adjs = numToAdjs.get(tail);
27            if (adjs[0] === prev) {
28                ans.push(adjs[1]);
29            } else {
30                ans.push(adjs[0]);
31            }
32        }
33        
34        return ans;
35    }
36};

Solution in C++

1#include <unordered_map>
2#include <vector>
3
4class Solution {
5public:
6    vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
7        unordered_map<int, vector<int>> numToAdjs;
8        
9        for (const vector<int>& pair : adjacentPairs) {
10            int u = pair[0];
11            int v = pair[1];
12            numToAdjs[u].push_back(v);
13            numToAdjs[v].push_back(u);
14        }
15        
16        vector<int> ans;
17        for (const auto& kv : numToAdjs) {
18            int num = kv.first;
19            const vector<int>& adjs = kv.second;
20            if (adjs.size() == 1) {
21                ans.push_back(num);
22                ans.push_back(adjs[0]);
23                break;
24            }
25        }
26        
27        while (ans.size() < adjacentPairs.size() + 1) {
28            int tail = ans.back();
29            int prev = ans[ans.size() - 2];
30            const vector<int>& adjs = numToAdjs[tail];
31            if (adjs[0] == prev) {
32                ans.push_back(adjs[1]);
33            } else {
34                ans.push_back(adjs[0]);
35            }
36        }
37        
38        return ans;
39    }
40};

Solution in C#

1using System.Collections.Generic;
2
3public class Solution {
4    public int[] RestoreArray(int[][] adjacentPairs) {
5        var numToAdjs = new Dictionary<int, List<int>>();
6        
7        foreach (var pair in adjacentPairs) {
8            int u = pair[0];
9            int v = pair[1];
10            if (!numToAdjs.ContainsKey(u)) numToAdjs[u] = new List<int>();
11            if (!numToAdjs.ContainsKey(v)) numToAdjs[v] = new List<int>();
12            numToAdjs[u].Add(v);
13            numToAdjs[v].Add(u);
14        }
15        
16        var ans = new int[adjacentPairs.Length + 1];
17        foreach (var kv in numToAdjs) {
18            int num = kv.Key;
19            var adjs = kv.Value;
20            if (adjs.Count == 1) {
21                ans[0] = num;
22                ans[1] = adjs[0];
23                break;
24            }
25        }
26        
27        for (int i = 2; i < ans.Length; i++) {
28            int tail = ans[i - 1];
29            int prev = ans[i - 2];
30            var adjs = numToAdjs[tail];
31            if (adjs[0] == prev) {
32                ans[i] = adjs[1];
33            } else {
34                ans[i] = adjs[0];
35            }
36        }
37        
38        return ans;
39    }
40}

Conclusion

This problem can be solved by using a hash map to store the adjacent pairs and then building the original array by finding an element with only one neighbor. This method is efficient as it has a time complexity of O(N), where N is the length of the input array adjacentPairs.