Skip to content

1743. Restore the Array From Adjacent Pairs 👍

  • Time: $O(n)$
  • Space: $O(n)$
 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
  }
};

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
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;
  }
}

 1
 2
 3
 4
 5
 6
 7
 8
 9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
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