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

SimplyLeet
TagsCompaniesDisclaimersPrivacyTermsContactAbout Us

Restore the Array From Adjacent Pairs

Number: 1866

Difficulty: Medium

Paid? No

Companies: Google, Robinhood

Problem Description

Given a list of adjacent pairs, where each pair represents two consecutive elements from an unknown array of unique integers, restore the original array. Each pair can appear in any order, and the endpoints of the array (which have only one adjacent neighbor) must be identified to begin reconstruction.

Key Insights

  • The array forms a chain-like structure.
  • All elements except the endpoints appear in exactly two pairs.
  • Endpoints are the elements that appear only once.
  • Use a hashmap (adjacency list) to track neighbors.
  • Traverse the chain starting from an endpoint, avoiding backtracking, to reconstruct the original array.

Space and Time Complexity

Time Complexity: O(n) - We traverse the list of pairs and then reconstruct the array in one pass. Space Complexity: O(n) - We store all the elements and their neighbors in a hashmap and the final array.

Solution

We first create a hashmap to map each element to its adjacent elements. Since the endpoints are unique in that they only have one neighbor, we locate one of them to serve as the start of our traversal. Then, we iteratively traverse from the current element to its neighbor (ignoring the element we just came from) until we reconstruct the entire array. This approach works efficiently given the constraints.

Code Solutions

# Python code solution with line-by-line comments

def restoreArray(adjacentPairs):
    # Create a hashmap to store each element's neighboring elements
    neighbors = {}
    for x, y in adjacentPairs:
        if x not in neighbors:
            neighbors[x] = []
        if y not in neighbors:
            neighbors[y] = []
        neighbors[x].append(y)
        neighbors[y].append(x)

    # Find an endpoint: element with only one neighbor
    start = None
    for key in neighbors:
        if len(neighbors[key]) == 1:
            start = key
            break

    # Initialize the result array with size n
    n = len(adjacentPairs) + 1
    result = [start]
    prev = None

    # Traverse the chain to restore the full array
    while len(result) < n:
        for neighbor in neighbors[start]:
            if neighbor != prev:
                result.append(neighbor)
                prev, start = start, neighbor
                break

    return result

# Example Usage:
print(restoreArray([[2,1],[3,4],[3,2]]))
← Back to All Questions