1743. Restore the Array From Adjacent Pairs LeetCode Solution

Last updated: February 24, 2025

In this guide, you will get 1743. Restore the Array From Adjacent Pairs LeetCode Solution with the best time and space complexity. The solution to Restore the Array From Adjacent Pairs problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.

Problem Statement
Complexity Analysis
Restore the Array From Adjacent Pairs solution in C++
Restore the Array From Adjacent Pairs solution in Java
Restore the Array From Adjacent Pairs solution in Python
Additional Resources

1743. Restore the Array From Adjacent Pairs LeetCode Solution image

Problem Statement of Restore the Array From Adjacent Pairs

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.

Complexity Analysis

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

1743. Restore the Array From Adjacent Pairs LeetCode Solution in C++

class Solution {
 public:
  vector<int> restoreArray(vector<vector<int>>& adjacentPairs) {
    vector<int> ans;
    unordered_map<int, vector<int>> numToAdjs;

    for (const vector<int>& pair : adjacentPairs) {
      const int u = pair[0];
      const int v = pair[1];
      numToAdjs[u].push_back(v);
      numToAdjs[v].push_back(u);
    }

    for (const auto& [num, adjs] : numToAdjs)
      if (adjs.size() == 1) {
        ans.push_back(num);
        ans.push_back(adjs[0]);
        break;
      }

    while (ans.size() < adjacentPairs.size() + 1) {
      const int tail = ans.back();
      const int prev = ans[ans.size() - 2];
      const vector<int>& adjs = numToAdjs[tail];
      if (adjs[0] == prev)
        ans.push_back(adjs[1]);
      else
        ans.push_back(adjs[0]);
    }

    return ans;
  }
};
/* code provided by PROGIEZ */

1743. Restore the Array From Adjacent Pairs LeetCode Solution in Java

class Solution {
  public int[] restoreArray(int[][] adjacentPairs) {
    int[] ans = new int[adjacentPairs.length + 1];
    int i = 0; // ans' index
    Map<Integer, List<Integer>> numToAdjs = new HashMap<>();

    for (int[] pair : adjacentPairs) {
      numToAdjs.putIfAbsent(pair[0], new ArrayList<>());
      numToAdjs.putIfAbsent(pair[1], new ArrayList<>());
      numToAdjs.get(pair[0]).add(pair[1]);
      numToAdjs.get(pair[1]).add(pair[0]);
    }

    for (Map.Entry<Integer, List<Integer>> entry : numToAdjs.entrySet())
      if (entry.getValue().size() == 1) {
        ans[i++] = entry.getKey();
        ans[i++] = entry.getValue().get(0);
        break;
      }

    while (i < adjacentPairs.length + 1) {
      final int tail = ans[i - 1];
      final int prev = ans[i - 2];
      List<Integer> adjs = numToAdjs.get(tail);
      if (adjs.get(0) == prev)
        ans[i++] = adjs.get(1);
      else
        ans[i++] = adjs.get(0);
    }

    return ans;
  }
}
// code provided by PROGIEZ

1743. Restore the Array From Adjacent Pairs LeetCode Solution in Python

class Solution:
  def restoreArray(self, adjacentPairs: list[list[int]]) -> list[int]:
    ans = []
    numToAdjs = collections.defaultdict(list)

    for a, b in adjacentPairs:
      numToAdjs[a].append(b)
      numToAdjs[b].append(a)

    for num, adjs in numToAdjs.items():
      if len(adjs) == 1:
        ans.append(num)
        ans.append(adjs[0])
        break

    while len(ans) < len(adjacentPairs) + 1:
      tail = ans[-1]
      prev = ans[-2]
      adjs = numToAdjs[tail]
      if adjs[0] == prev:  # adjs[0] is already used
        ans.append(adjs[1])
      else:
        ans.append(adjs[0])

    return ans
 # code by PROGIEZ

Additional Resources

Happy Coding! Keep following PROGIEZ for more updates and solutions.

Table of Contents