We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Restore the Array From Adjacent Pairs

Difficulty: Medium

Problem 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. Return the original array nums. If there are multiple solutions, return any of them.

Key Insights

  • Each element in the original array appears in exactly two adjacent pairs, except for the elements at the ends which appear in only one pair.
  • We can use a graph representation where each number is a node and the pairs represent edges connecting these nodes.
  • To reconstruct the original array, we can traverse the graph starting from one of the endpoints.

Space and Time Complexity

Time Complexity: O(n)
Space Complexity: O(n)

Solution

To solve this problem, we will represent the pairs as a graph using an adjacency list. Each number will be a node, and the pairs will create edges between them. We will then identify one of the endpoints (a number that appears only once in the adjacency list) and perform a depth-first search (DFS) or breadth-first search (BFS) to traverse through the graph and reconstruct the original array.

Code Solutions

from collections import defaultdict

def restoreArray(adjacentPairs):
    graph = defaultdict(list)
    
    # Build the graph
    for u, v in adjacentPairs:
        graph[u].append(v)
        graph[v].append(u)
    
    # Find one endpoint (a number that has only one neighbor)
    start = None
    for key in graph:
        if len(graph[key]) == 1:
            start = key
            break
    
    # Perform DFS to reconstruct the array
    result = []
    visited = set()

    def dfs(node):
        visited.add(node)
        result.append(node)
        for neighbor in graph[node]:
            if neighbor not in visited:
                dfs(neighbor)

    dfs(start)
    return result
← Back to All Questions