Welcome to Subscribe On Youtube
1743. Restore the Array From Adjacent Pairs
Description
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] = [ui, vi] indicates that the elements ui and vi 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 == nadjacentPairs.length == n - 1adjacentPairs[i].length == 22 <= n <= 105-105 <= nums[i], ui, vi <= 105- There exists some
numsthat hasadjacentPairsas its pairs.
Solutions
Traverse the graph from the point where the degree is one.
-
class 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; } } -
class 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; } }; -
class 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 -
func restoreArray(adjacentPairs [][]int) []int { n := len(adjacentPairs) + 1 g := map[int][]int{} for _, e := range adjacentPairs { a, b := e[0], e[1] g[a] = append(g[a], b) g[b] = append(g[b], a) } ans := make([]int, n) for k, v := range g { if len(v) == 1 { ans[0] = k ans[1] = v[0] break } } for i := 2; i < n; i++ { v := g[ans[i-1]] ans[i] = v[0] if v[0] == ans[i-2] { ans[i] = v[1] } } return ans } -
public 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; } }