MediumNo. 1743
Restore the Array From Adjacent Pairs — LeetCode 1743 Python Solution
- Pattern
- Depth-First Search
- Topics
- Depth-First Search, Array, Hash Table
- Reading time
- 3 min
- Source
- leetcode.com
The problem
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.
Example
- Input
- adjacentPairs = [[2,1],[3,4],[3,2]]
- Output
- [1,2,3,4]
- Explanation
- This array has all its adjacent pairs in adjacentPairs.
Python solution
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 ansComplexity
- Time
- O(n)
- Space · auxiliary
- O(n)
Pattern: Depth-First Search
Follow one path to its end before trying the next — the default way to explore a graph. LeetCode 1743. Restore the Array From Adjacent Pairs is filed here because LeetCode tags it Depth-First Search, which is the vocabulary this hub collects.
The depth-first search guide has the Python template for the pattern and the 366 LeetCode problems that use it.
Related problems
| No. | Problem | Difficulty |
|---|---|---|
| 0690 | Employee Importance | Medium |
| 0721 | Accounts Merge | Medium |
| 0839 | Similar String Groups | Hard |
| 0924 | Minimize Malware Spread | Hard |
| 0928 | Minimize Malware Spread II | Hard |
| 0959 | Regions Cut By Slashes | Medium |
Frequently asked questions
- How hard is LeetCode 1743. Restore the Array From Adjacent Pairs?
LeetCode 1743. Restore the Array From Adjacent Pairs is rated Medium on LeetCode.
- What is the time complexity of LeetCode 1743. Restore the Array From Adjacent Pairs?
The Python solution on this page runs in O(n).
- What is the space complexity of LeetCode 1743. Restore the Array From Adjacent Pairs?
The Python solution on this page uses O(n) auxiliary space.
- What topics does LeetCode 1743. Restore the Array From Adjacent Pairs cover?
LeetCode 1743. Restore the Array From Adjacent Pairs is tagged Depth-First Search, Array and Hash Table on LeetCode.