Welcome to Subscribe On Youtube
Formatted question description: https://leetcode.ca/all/1743.html
1743. Restore the Array From Adjacent Pairs
Level
Medium
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] = [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 == nadjacentPairs.length == n - 1adjacentPairs[i].length == 22 <= n <= 10^5-10^5 <= nums[i], ui, vi <= 10^5- There exists some
numsthat hasadjacentPairsas its pairs.
Solution
All elements in nums occur twice in adjacentPairs except the two elements that are at the start and the end of nums. Therefore, start from the two elements that occur only once in adjacentPairs, put them at index 0 and index n - 1 of nums respectively. The two elements at indices 1 and n - 2 can be determined as well. For i from 1 to n - 2, obtain the adjacent numbers of nums[i] and set nums[i + 1] as the remaining element (that is differnet from nums[i - 1]). Finally, return nums.
-
class Solution { public int[] restoreArray(int[][] adjacentPairs) { Map<Integer, List<Integer>> map = new HashMap<Integer, List<Integer>>(); for (int[] adjacentPair : adjacentPairs) { int num1 = adjacentPair[0], num2 = adjacentPair[1]; List<Integer> list1 = map.getOrDefault(num1, new ArrayList<Integer>()); List<Integer> list2 = map.getOrDefault(num2, new ArrayList<Integer>()); list1.add(num2); list2.add(num1); map.put(num1, list1); map.put(num2, list2); } int length = adjacentPairs.length + 1; int[] nums = new int[length]; boolean flag = false; Set<Integer> set = map.keySet(); for (int num : set) { List<Integer> list = map.get(num); if (list.size() == 1) { if (!flag) { nums[0] = num; nums[1] = list.get(0); flag = true; } else { nums[length - 1] = num; nums[length - 2] = list.get(0); } } } for (int i = 1; i < length - 1; i++) { int num = nums[i]; List<Integer> list = map.get(num); for (int adjacent : list) { if (adjacent != nums[i - 1]) { nums[i + 1] = adjacent; break; } } } return nums; } } ############ 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: 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 ############ # 1743. Restore the Array From Adjacent Pairs # https://leetcode.com/problems/restore-the-array-from-adjacent-pairs class Solution: def restoreArray(self, adjacentPairs: List[List[int]]) -> List[int]: neigh = collections.defaultdict(list) res = [] for a,b in adjacentPairs: neigh[a].append(b) neigh[b].append(a) for nei in neigh: if len(neigh[nei]) == 1: res.append(nei) res.append(neigh[nei][0]) break while len(res) < len(adjacentPairs) + 1: prev, head = res[len(res)-2], res[-1] nei = neigh[head] if nei[0] == prev: res.append(nei[1]) else: res.append(nei[0]) return res -
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; } }; -
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; } }