# Solving Leetcode Interviews in Seconds with AI: Restore the Array From Adjacent Pairs


	# Introduction
	In this blog post, we will explore how to solve the LeetCode problem "1743" using AI. LeetCode is a popular platform for preparing for coding interviews, and with the help of AI tools like [Chatmagic](https://www.chatmagic.app), we can generate solutions quickly and efficiently - helping you pass the interviews and get the job offer without having to study for months.

	# 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] = [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.   Example 1:  Input: adjacentPairs = [[2,1],[3,4],[3,2]] Output: [1,2,3,4] Explanation: 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] Explanation: 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]    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.  

	# Explanation
	Here's the breakdown of the approach and the Python code:

*   **High-Level Approach:**
    *   Build an adjacency list (a graph representation) from the `adjacentPairs`.
    *   Identify the start node(s) - nodes with degree 1 (appearing only once in the adjacency list). This is because the array starts and ends with such elements.
    *   Perform a Depth-First Search (DFS) or Breadth-First Search (BFS) starting from one of the start nodes to reconstruct the array.

*   **Complexity:**
    *   Runtime Complexity: O(n), where n is the number of elements in the array.
    *   Storage Complexity: O(n)

	
	# Code
	```python
	def restoreArray(adjacentPairs):
    """
    Restores the original array from adjacent pairs.

    Args:
        adjacentPairs: A list of adjacent pairs.

    Returns:
        The original array.
    """

    adj_list = {}
    for u, v in adjacentPairs:
        if u not in adj_list:
            adj_list[u] = []
        if v not in adj_list:
            adj_list[v] = []
        adj_list[u].append(v)
        adj_list[v].append(u)

    start_nodes = []
    for node, neighbors in adj_list.items():
        if len(neighbors) == 1:
            start_nodes.append(node)

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

    dfs(start_nodes[0])  # Start DFS from the first start node

    return result
	```