Restore the Array From Adjacent Pairs
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]This array has all its adjacent pairs in
adjacentPairs, and 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]There can be negative numbers, and another valid solution is
[-3, 1, 4, -2].Constraints
- nums.length == n
- adjacentPairs.length == n - 1
- adjacentPairs[i].length == 2
- 2 <= n <= 10^5
- -10^5 <= nums[i], ui, vi <= 10^5
- There exists some nums that has adjacentPairs as its pairs.
Asked at 9 companies
Practice questions like this out loud in a mock coding interview with a live AI interviewer. First one free.