What is the time complexity of Restore the Array From Adjacent Pairs?

The optimal solution has a time complexity of O(n).

What data structures are used to solve Restore the Array From Adjacent Pairs?

This problem uses Array, Hash Table, Depth-First Search. Understanding these concepts is essential for solving this Medium problem efficiently.

What are the key insights for solving Restore the Array From Adjacent Pairs?

Insight 1: The `adjacentPairs` effectively form a graph where each number is a node and each pair represents an edge. Since each number in `nums` is unique, there are exactly two nodes (the start and end) which have only one neighbor, corresponding to the first and last elements of the original array. Insight 2: We can use a hash map (or dictionary) to represent the adjacency list of the graph. This allows us to quickly find the neighbors of a given number.

Which companies ask LeetCode 1743. Restore the Array From Adjacent Pairs in interviews?

This problem is frequently asked at Robinhood.

JavaScript is required for the full interactive experience. However, all content is accessible without JavaScript.

Restore the Array From Adjacent Pairs - LeetCode 1743 Solution

Restore the Array From Adjacent Pairs - Complete Solution Guide

Restore the Array From Adjacent Pairs is LeetCode problem 1743, a Medium level challenge. This complete guide provides step-by-step explanations, multiple solution approaches, and optimized code in python3, java, cpp, c.

Problem Statement

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 . 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

Detailed Explanation

The problem presents a scenario where we've forgotten an array of unique integers (`nums`), but we remember all pairs of adjacent elements in the array. We are given these pairs in the `adjacentPairs` array. The goal is to reconstruct the original `nums` array given the `adjacentPairs`. The pairs can be in any order (e.g., `[a, b]` or `[b, a]`). We are guaranteed that a solution exists, and if multiple solutions exist, we can return any of them.

Solution Approach

The provided solution uses a graph-based approach. First, it builds an adjacency list representation of the graph from the `adjacentPairs`. Then, it finds a starting node (a node with only one neighbor, representing one end of the array). Finally, it traverses the graph, reconstructing the array by following the neighbors, while avoiding revisiting the previous node.

Step-by-Step Algorithm

Step 1: Create an adjacency list (graph) from the `adjacentPairs`. For each pair `[u, v]`, add `v` to the list of neighbors of `u`, and `u` to the list of neighbors of `v`.
Step 2: Find a starting node. Iterate through the graph and identify a node that has only one neighbor (degree 1). This node will be one of the ends of the original array.
Step 3: Initialize an array `result` of the correct size to store the reconstructed array. Also, initialize `curr` to the starting node and `prev` to a value that is guaranteed to be different from any node value (e.g., infinity or a very large number) to avoid going back to the starting node in the first iteration.
Step 4: Iterate through the `result` array. In each iteration, set `result[i]` to `curr`. Then, find the neighbor of `curr` that is not equal to `prev`. Update `prev` to `curr` and `curr` to the found neighbor.
Step 5: Return the `result` array.

Key Insights

Insight 1: The `adjacentPairs` effectively form a graph where each number is a node and each pair represents an edge. Since each number in `nums` is unique, there are exactly two nodes (the start and end) which have only one neighbor, corresponding to the first and last elements of the original array.
Insight 2: We can use a hash map (or dictionary) to represent the adjacency list of the graph. This allows us to quickly find the neighbors of a given number.
Insight 3: Since there are two possible start/end points in the array (each having degree 1), and each adjacent pair could be stored as `[u, v]` or `[v, u]`, there could be multiple solutions to the problem. The algorithm only needs to return any one of the valid solutions.

Complexity Analysis

Time Complexity: O(n)

Space Complexity: O(n)

Topics

This problem involves: Array, Hash Table, Depth-First Search.

Companies

Asked at: Robinhood.

Restore the Array From Adjacent Pairs | LeetCode 1743

Medium

Array Hash Table Depth-First Search

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

Solution Code

Available in:

import java.util.*;

class Solution {
    public int[] restoreArray(int[][] adjacentPairs) {
        Map<Integer, List<Integer>> graph = new HashMap<>();
        for (int[] pair : adjacentPairs) {
            int u = pair[0];
            int v = pair[1];
            graph.computeIfAbsent(u, k -> new ArrayList<>()).add(v);
            graph.computeIfAbsent(v, k -> new ArrayList<>()).add(u);
        }

        int startNode = -1;
        for (int node : graph.keySet()) {
            if (graph.get(node).size() == 1) {
                startNode = node;
                break;
            }
        }

        int n = adjacentPairs.length + 1;
        int[] result = new int[n];
        int curr = startNode;
        int prev = Integer.MAX_VALUE;

        for (int i = 0; i < n; i++) {
            result[i] = curr;
            for (int neighbor : graph.get(curr)) {
                if (neighbor != prev) {
                    prev = curr;
                    curr = neighbor;
                    break;
                }
            }
        }

        return result;
    }
}

View Full Solution on GitHubGitHub Solution View on LeetCodeLeetCode

Problem Info

Description

Problem 1743: Restore the Array From Adjacent Pairs - Detailed explanation and solution approaches.

Topics

Array Hash Table Depth-First Search

Companies

Robinhood

Stats

Difficulty:Medium

Languages:4

Companies:1

Problem #:1743

Problem Explanation

💡

Think Before You Code

🤔 Ask Yourself

→What is the input? What output do I need?
→Can I solve a smaller version of this problem first?
→What patterns have I seen in similar problems?

✏️ Try This First

Before looking at the solution, try to solve it on paper with a simple example!

🚀 Try on LeetCode

Solution Approach

📋

Step-by-Step Solution

5 steps

1
Step 1: Create an adjacency list (graph) from the `adjacentPairs`. For each pair `[u, v]`, add `v` to the list of neighbors of `u`, and `u` to the list of neighbors of `v`.
2
Step 2: Find a starting node. Iterate through the graph and identify a node that has only one neighbor (degree 1). This node will be one of the ends of the original array.
3
Step 3: Initialize an array `result` of the correct size to store the reconstructed array. Also, initialize `curr` to the starting node and `prev` to a value that is guaranteed to be different from any node value (e.g., infinity or a very large number) to avoid going back to the starting node in the first iteration.
4
Step 4: Iterate through the `result` array. In each iteration, set `result[i]` to `curr`. Then, find the neighbor of `curr` that is not equal to `prev`. Update `prev` to `curr` and `curr` to the found neighbor.
5
Step 5: Return the `result` array.

💡

Pro Tip for Students

Try tracing through each step with a small example on paper before coding. Understanding "why" each step happens is more important than memorizing the code!

⚡

Complexity Analysis

⏱️

Time Complexity

O(n)

👍 Linear - Good! Visits each element once.

💾

Space Complexity

O(n)

📦 Linear space - Memory grows with input size.

📝

Why?

The time complexity is determined by the graph construction and traversal which are linear with the number of adjacent pairs (which is one less than the size of the original array). The space complexity is determined by the storage requirements for the adjacency list and the result array. The adjacency list stores each node and its neighbors. The number of neighbors is limited to at most two, as each element is adjacent to at most two other elements. The result array stores the reconstructed original array of size n.

📖New to Big O? Click to learn more

Big O Notation - Quick Guide

O(1)Best - Instant

O(log n)Excellent - Binary Search

O(n)Good - One loop

O(n log n)OK - Sorting

O(n²)Slow - Nested loops

O(2ⁿ)Very Slow - Recursion

Alternative Approaches

Depth-First Search (DFS)

Instead of directly iterating through the graph, we can use DFS to traverse the graph and build the array. We start from a node with degree 1 (the start node) and recursively explore its neighbors, adding them to the array. We keep track of the visited nodes to avoid cycles.

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

Trade-offs: DFS and iterative approaches are nearly identical in terms of performance for this problem. The iterative method is often slightly faster due to lower overhead compared to the recursive calls in DFS.

✨

Key Insights

1Insight 1: The `adjacentPairs` effectively form a graph where each number is a node and each pair represents an edge. Since each number in `nums` is unique, there are exactly two nodes (the start and end) which have only one neighbor, corresponding to the first and last elements of the original array.
2Insight 2: We can use a hash map (or dictionary) to represent the adjacency list of the graph. This allows us to quickly find the neighbors of a given number.
3Insight 3: Since there are two possible start/end points in the array (each having degree 1), and each adjacent pair could be stored as `[u, v]` or `[v, u]`, there could be multiple solutions to the problem. The algorithm only needs to return any one of the valid solutions.

📚

Key Terms Explained

For Students

Array

A collection of items stored at contiguous memory locations. Like a row of boxes.

Hash Table

A data structure that maps keys to values for quick lookup. Like a dictionary!

Edge Cases

Edge case 1: `adjacentPairs` is empty. Although constraints say n >= 2, if the input `adjacentPairs` is empty, it implies that `n = 1`, and thus there are no adjacent pairs, and should only be one element. However, the prompt says there must exist *some* `nums` array that has `adjacentPairs` as it's pairs. The problem statement indicates that `adjacentPairs` always represents `n - 1` where `n` is the length of the array so there is an implicit assumption `adjacentPairsSize` must be greater than or equal to 1. If the input is an empty `adjacentPairs` array, the algorithm does not handle that correctly. It's expected to handle an edge case where `n = 2` and the input contains a single pair `[[x, y]]`.
Edge case 2: The input guarantees that there exists *some* `nums` and thus there will always be a valid startNode which is a node with degree 1.

⚠️

Common Mistakes to Avoid

✗Common mistake 1: Not handling the case where the input graph might have multiple components (although this is not possible given problem's constraint). Beginners may forget to check that all nodes are reachable from the start node.

✗Common mistake 2: Forgetting to keep track of the previously visited node to avoid going back and forth between two adjacent nodes infinitely.

✅

Learning Tip

Every mistake is a learning opportunity! When you make an error, understand why it happened before moving on.

🌍

Where is This Used in Real Life?

💼Real-world scenario 1: Reconstructing a path from a series of connected road segments. Each road segment can be represented as a pair of adjacent locations, and the problem becomes finding the order of locations along the path.

🏦Real-world scenario 2: Genome sequencing where you have overlapping DNA fragments and want to reconstruct the original DNA sequence. The overlapping fragments are the adjacent pairs and the DNA sequence is what you are trying to restore.

💡Understanding real-world applications helps you see the "why" behind algorithms. It's not just about passing interviews—these concepts power the apps and websites you use every day!

Author's Notes

💡 Key Insight

When dealing with arrays, always consider if sorting would simplify the problem. Many array problems have O(n) solutions using hash maps or two-pointer technique.

🎯 Interview Tip

Medium problems are the bread and butter of technical interviews. Practice explaining your approach before coding.

⚠️ Watch Out

Off-by-one errors are the most common mistake. Double-check your loop bounds and array indices.

Written by Saswata Mondal

Software Engineer • Algorithms Enthusiast • Interview Coach

👨‍💻

About the Author

👨‍💻

Saswata MondalAuthor400+ LC Problems

B.Tech CSE, IEM Kolkata | LeetCode Rating: 1672 (Top 15%)

Certified: IBM Java Developer, NPTEL Programming in Java

Last updated: October 2, 2024LeetCode Profile GitHub

This solution has been crafted based on my experience solving 400+ LeetCode problems. Each explanation is designed to help you understand the underlying concepts, not just memorize the code.

Community Tips & Insights

Try solving this without using extra space first. It's a great exercise for understanding the underlying pattern.

@CodeNinjaJul 14

In a real interview, always clarify constraints first. Ask about input size and value ranges.

@TechLeadJul 7

Don't forget to handle the edge case when the input is empty. Many candidates miss this in interviews.

@DevExpert92Jun 30

❓

Frequently Asked Questions

When should I use in-place modification vs creating a new array?

Use in-place modification when space complexity matters (O(1) space requirement) and the original array can be modified. Create a new array when you need to preserve the original data or when the problem involves significant restructuring that would complicate in-place logic.

How do I choose between a hash map and a hash set?

Use a hash set when you only need to track presence/absence of elements (like detecting duplicates). Use a hash map when you need to associate values with keys (like counting frequencies or storing indices). Hash sets use less memory since they only store keys.

How much time should I spend on a medium problem in interviews?

In a 45-minute interview, aim for: 5-10 minutes understanding and clarifying, 5-10 minutes discussing approach, 20-25 minutes coding, and 5-10 minutes testing. If stuck after 15 minutes of thinking, verbalize your thought process and ask for hints.

What is the importance of time and space complexity analysis?

Complexity analysis is crucial because: 1) Interviewers always ask about it, 2) It helps you choose between approaches, 3) It demonstrates CS fundamentals. Always state both time and space complexity, and be prepared to explain how you derived them.

What is the optimal approach for "Restore the Array From Adjacent Pairs"?

For this medium-level Array problem, the key is to identify the core pattern. Analyze the input constraints to determine acceptable time complexity. Consider whether hash table techniques can optimize the solution. Always handle edge cases and validate your approach with examples before coding.

🤖 Need help with this problem?