Skip to content

2097. Valid Arrangement of Pairs 👍

  • Time: $O(|V| + |E|)$
  • Space: $O(|V| + |E|)$
 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
34
35
36
37
38
39
40
41
42
43
44
class Solution {
 public:
  vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
    vector<vector<int>> ans;
    unordered_map<int, stack<int>> graph;
    unordered_map<int, int> outDegree;
    unordered_map<int, int> inDegrees;

    for (const vector<int>& pair : pairs) {
      const int start = pair[0];
      const int end = pair[1];
      graph[start].push(end);
      ++outDegree[start];
      ++inDegrees[end];
    }

    const int startNode = getStartNode(graph, outDegree, inDegrees, pairs);
    euler(graph, startNode, ans);
    ranges::reverse(ans);
    return ans;
  }

 private:
  int getStartNode(const unordered_map<int, stack<int>>& graph,
                   unordered_map<int, int>& outDegree,
                   unordered_map<int, int>& inDegrees,
                   const vector<vector<int>>& pairs) {
    for (const auto& [u, _] : graph)
      if (outDegree[u] - inDegrees[u] == 1)
        return u;
    return pairs[0][0];  // Arbitrarily choose a node.
  }

  void euler(unordered_map<int, stack<int>>& graph, int u,
             vector<vector<int>>& ans) {
    auto& stack = graph[u];
    while (!stack.empty()) {
      const int v = stack.top();
      stack.pop();
      euler(graph, v, ans);
      ans.push_back({u, v});
    }
  }
};

 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
34
35
36
37
38
39
class Solution {
  public int[][] validArrangement(int[][] pairs) {
    List<int[]> ans = new ArrayList<>();
    Map<Integer, Deque<Integer>> graph = new HashMap<>();
    Map<Integer, Integer> outDegree = new HashMap<>();
    Map<Integer, Integer> inDegrees = new HashMap<>();

    for (int[] pair : pairs) {
      final int start = pair[0];
      final int end = pair[1];
      graph.putIfAbsent(start, new ArrayDeque<>());
      graph.get(start).push(end);
      outDegree.merge(start, 1, Integer::sum);
      inDegrees.merge(end, 1, Integer::sum);
    }

    final int startNode = getStartNode(graph, outDegree, inDegrees, pairs);
    euler(graph, startNode, ans);
    Collections.reverse(ans);
    return ans.stream().toArray(int[][] ::new);
  }

  private int getStartNode(Map<Integer, Deque<Integer>> graph, Map<Integer, Integer> outDegree,
                           Map<Integer, Integer> inDegrees, int[][] pairs) {
    for (final int u : graph.keySet())
      if (outDegree.getOrDefault(u, 0) - inDegrees.getOrDefault(u, 0) == 1)
        return u;
    return pairs[0][0]; // Arbitrarily choose a node.
  }

  private void euler(Map<Integer, Deque<Integer>> graph, int u, List<int[]> ans) {
    Deque<Integer> stack = graph.get(u);
    while (stack != null && !stack.isEmpty()) {
      final int v = stack.pop();
      euler(graph, v, ans);
      ans.add(new int[] {u, v});
    }
  }
}

 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
class Solution:
  def validArrangement(self, pairs: list[list[int]]) -> list[list[int]]:
    ans = []
    graph = collections.defaultdict(list)
    outDegree = collections.Counter()
    inDegrees = collections.Counter()

    for start, end in pairs:
      graph[start].append(end)
      outDegree[start] += 1
      inDegrees[end] += 1

    def getStartNode() -> int:
      for u in graph.keys():
        if outDegree[u] - inDegrees[u] == 1:
          return u
      return pairs[0][0]  # Arbitrarily choose a node.

    def euler(u: int) -> None:
      stack = graph[u]
      while stack:
        v = stack.pop()
        euler(v)
        ans.append([u, v])

    euler(getStartNode())
    return ans[::-1]