#1743

Medium

auto_awesomeArray scanning plus hash lookup

LeetCode Problem Workspace

Restore the Array From Adjacent Pairs

Restore the Array From Adjacent Pairs reconstructs a sequence using adjacent element pairs. Efficient hash lookups and array scanning help solve this.

array hash table depth first search

Problem Statement

You have a sequence of n unique integers stored in an array nums, but you’ve forgotten its exact order. However, you remember all pairs of adjacent elements from the array, given as a 2D integer array adjacentPairs, where each pair represents two adjacent elements in nums.

The array nums must be restored by reconstructing it using the provided adjacentPairs. Every adjacent pair in nums is guaranteed to appear in adjacentPairs, either as [nums[i], nums[i+1]] or [nums[i+1], nums[i]]. Your task is to determine the original order of nums efficiently.

Examples

Example 1

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

Output: [1,2,3,4]

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]

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]

Example details omitted.

Constraints

nums.length == n
adjacentPairs.length == n - 1
adjacentPairs[i].length == 2
2 <= n <= 105
-105 <= nums[i], ui, vi <= 105
There exists some nums that has adjacentPairs as its pairs.

Solution Approach

Identify the First Element

The first element of the array will only appear once in the adjacentPairs. Use this fact to quickly identify the starting point for the array reconstruction.

Use Hash Tables for Quick Lookups

Create a hash table to store adjacent pairs of elements. This allows you to efficiently find neighbors for any given element while reconstructing the array.

Array Scanning and DFS Traversal

Once you have identified the first element, use array scanning or Depth-First Search (DFS) to traverse the array, ensuring each adjacent element is visited in the correct order.

Complexity Analysis

Metric	Value
Time	O(n)
Space	O(n)

Time complexity is O(n) because each element in adjacentPairs is processed once, and space complexity is O(n) due to the storage required for the hash table and the reconstructed array.

What Interviewers Usually Probe

Candidate identifies the first element in adjacentPairs.
Candidate efficiently uses a hash table to reconstruct the array.
Candidate uses DFS or array scanning to correctly traverse the array.

Common Pitfalls or Variants

Common pitfalls

Forgetting to check for the first element in adjacentPairs.
Misunderstanding the directionality of pairs or their possible order.
Not efficiently using hash tables for lookups, leading to suboptimal performance.

Follow-up variants

Allow duplicate elements in nums, complicating the process of finding the first element.
Allow the adjacent pairs to be given in a random order, testing the robustness of the solution.
Require reconstructing the array in reverse order, adjusting traversal logic.

FAQ

How can I restore the array from adjacent pairs?

The key is identifying the first element, which only appears once in the pairs, and using hash tables and DFS to reconstruct the array.

What is the time complexity of this problem?

The time complexity is O(n), where n is the number of elements in the adjacentPairs array.

What is the optimal solution for restoring the array?

The optimal solution involves scanning the adjacentPairs for the first element, then using hash tables for quick lookups and DFS for array traversal.

How do adjacent pairs work in this problem?

Each pair in adjacentPairs represents two adjacent elements in the original array nums, and the goal is to reconstruct nums using these pairs.

What is the first step in solving the 'Restore the Array From Adjacent Pairs' problem?

The first step is to find the first element, which appears only once in the adjacentPairs, and use it as the starting point for reconstruction.

terminal

Solution

Solution 1

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

Solution 2

#### Python3

1

2

3

4

5

6

7

8

9

10

11

12

13

14

15

16

17

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

Continue Practicing

#1938 maximum genetic difference query #1993 operations on tree #1202 smallest string with swaps