Restore the Array From Adjacent Pairs - Practice Coding Problems

Restore the Array From Adjacent Pairs - 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.

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.

Input & Output

Example 1 — Basic Linear Chain

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

› Output: [2,1,3]

💡 Note: The pairs tell us 2 connects to 1, and 1 connects to 3. Since 2 and 3 each have only one neighbor, they are endpoints. Starting from endpoint 2: 2→1→3.

Example 2 — Longer Chain

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

› Output: [2,4,1,3]

💡 Note: Build graph: 4↔2, 4↔1, 1↔3. Endpoints are 2 and 3 (one neighbor each). Starting from 2: 2→4→1→3.

Example 3 — Two Elements

$ Input: adjacentPairs = [[100,200]]

› Output: [100,200]

💡 Note: Minimum case: only one pair means two adjacent elements. Both are endpoints, so either [100,200] or [200,100] is valid.

Constraints

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

Visualization

Tap to expand

Understanding the Visualization

Input

Adjacent pairs: [[2,1],[1,3]]

Process

Build graph: 2↔1↔3, find endpoints

Output

Restored array: [2,1,3]

Key Takeaway

🎯 Key Insight: The array forms a linear chain - find an endpoint and traverse to reconstruct the sequence

Asked in

f Facebook 15 G Google 12 a Amazon 8

The key insight is that this forms a linear chain where endpoints have exactly one neighbor while middle elements have two. Build an adjacency map from the pairs, find any endpoint (node with one connection), then traverse the chain. Best approach uses hash map with linear traversal - Time: O(n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Hash Map - Build Adjacency Graph	O(n)	O(n)	Build adjacency map, find endpoint with one neighbor, then traverse the chain
Brute Force - Try All Permutations	O(n! × n)	O(n)	Generate all possible arrays and check which one matches the adjacent pairs
DFS - Depth First Search	O(n)	O(n)	Use DFS to traverse the graph starting from any endpoint

Hash Map - Build Adjacency Graph — Algorithm Steps

Build adjacency map from pairs
Find a number with only one neighbor (endpoint)
Start from endpoint and traverse chain
Add each number to result while avoiding cycles

Visualization

Tap to expand

Step-by-Step Walkthrough

Build Graph

Create adjacency map from pairs

Find Endpoint

Number with only 1 neighbor

Traverse Chain

Follow connections to build result

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>

#define MAX_NODES 100000

struct Node {
    int neighbors[2];
    int count;
};

int* solution(int** adjacentPairs, int pairsSize, int* colSize, int* returnSize) {
    struct Node graph[MAX_NODES];
    int offset = 50000; // Handle negative numbers
    
    // Initialize
    for (int i = 0; i < MAX_NODES; i++) {
        graph[i].count = 0;
    }
    
    // Build adjacency list
    for (int i = 0; i < pairsSize; i++) {
        int a = adjacentPairs[i][0] + offset;
        int b = adjacentPairs[i][1] + offset;
        
        graph[a].neighbors[graph[a].count++] = adjacentPairs[i][1];
        graph[b].neighbors[graph[b].count++] = adjacentPairs[i][0];
    }
    
    // Find starting point
    int start = 0;
    for (int i = 0; i < MAX_NODES; i++) {
        if (graph[i].count == 1) {
            start = graph[i].neighbors[0];
            break;
        }
    }
    
    int* result = malloc((pairsSize + 1) * sizeof(int));
    result[0] = start;
    int prev = INT_MIN;
    int current = start;
    int size = 1;
    
    while (size < pairsSize + 1) {
        int currentIdx = current + offset;
        for (int i = 0; i < graph[currentIdx].count; i++) {
            int neighbor = graph[currentIdx].neighbors[i];
            if (neighbor != prev) {
                result[size++] = neighbor;
                prev = current;
                current = neighbor;
                break;
            }
        }
    }
    
    *returnSize = size;
    return result;
}

int main() {
    // Simplified input parsing for C
    printf("[4,2,3,1]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Single pass to build map O(n), single traversal O(n)

✓ Linear Growth

Space Complexity

O(n)

Hash map stores up to n numbers with their neighbors

⚡ Linearithmic Space

68.0K Views

Medium Frequency

~15 min Avg. Time

2.2K Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Hash Map - Build Adjacency Graph — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler