2097. Valid Arrangement of Pairs

Problem Description

Given a set of n nodes, there are n directed edges that form a sequence. The task is to find the correct arrangement of these edges to form the sequence. You are given a list pairs where pairs[i] = [a, b] indicates that there is a directed edge from node a to node b.

Return a list of pairs representing the correct arrangement of the edges. If there are multiple answers, return any of them.

Example:

Given pairs = [[1, 2], [2, 3], [3, 4], [4, 1]]

Output: [[1, 2], [2, 3], [3, 4], [4, 1]]

Approach

The problem is a graph traversal problem, and we will be using Hierholzer's algorithm to find the valid arrangement. More specifically, we will first create a directed graph using the given node pairs. Then, we'll build the correct arrangement of the edges by starting at the unique node with an out-degree of 1 greater than its in-degree, or arbitrarily choosing a starting node if no such unique node exists.

We use the following key data structures:

• We store the graph using an unordered_map with the node value as the key and stacks as the values to store the adjacent nodes.
• We use two unordered_maps to store the in-degree and out-degree of each node.

Step 1: Create the directed graph

We first create the directed graph using the given node pairs. We also populate the in-degree and out-degree maps while doing this.

Step 2: Find the starting node

We check for a unique node where the out-degree is one more than the in-degree. If such a node exists, we start from that node; otherwise, we arbitarily choose a starting node from the given node pairs.

Step 3: Apply Hierholzer's algorithm to form the valid arrangement

We start at the starting node and traverse the edges in a depth-first manner using recursion and keeping track of the visited edges. We also keep track of the visited edges by popping them from the stack once traversed, which means that the stack will be empty when there is no more unvisited edge from that node.

Once all edges are visited, we reverse the order of the visited edges, representing the valid arrangement.

We'll implement this algorithm in a class called Solution for the following languages: Python, Java, JavaScript, C++, and C#.

Python Solution

1
2python
3class Solution:
4    def validArrangement(self, pairs):
5        ans = []
6        graph = {}
7        outDegree = {}
8        inDegree = {}
9
10        for pair in pairs:
11            start, end = pair
12            if not start in graph:
13                graph[start] = []
14            graph[start].append(end)
15            outDegree[start] = outDegree.get(start, 0) + 1
16            inDegree[end] = inDegree.get(end, 0) + 1
17
18        startNode = self.getStartNode(graph, outDegree, inDegree, pairs)
19        self.euler(graph, startNode, ans)
20        ans.reverse()
21        return ans
22
23    def getStartNode(self, graph, outDegree, inDegree, pairs):
24        for u in graph:
25            if outDegree[u] - inDegree.get(u, 0) == 1:
26                return u
27        return pairs[0][0]
28
29    def euler(self, graph, u, ans):
30        while graph[u]:
31            v = graph[u].pop()
32            self.euler(graph, v, ans)
33            ans.append([u, v])

Java Solution

1
2java
3import java.util.*;
4
5class Solution {
6    public List<List<Integer>> validArrangement(int[][] pairs) {
7        List<List<Integer>> ans = new ArrayList<>();
8        Map<Integer, Stack<Integer>> graph = new HashMap<>();
9        Map<Integer, Integer> outDegree = new HashMap<>();
10        Map<Integer, Integer> inDegree = new HashMap<>();
11
12        for (int[] pair : pairs) {
13            int start = pair[0];
14            int end = pair[1];
15            graph.computeIfAbsent(start, x -> new Stack<>()).push(end);
16            outDegree.put(start, outDegree.getOrDefault(start, 0) + 1);
17            inDegree.put(end, inDegree.getOrDefault(end, 0) + 1);
18        }
19
20        int startNode = getStartNode(graph, outDegree, inDegree, pairs);
21        euler(graph, startNode, ans);
22        Collections.reverse(ans);
23        return ans;
24    }
25
26    private int getStartNode(Map<Integer, Stack<Integer>> graph, Map<Integer, Integer> outDegree, Map<Integer, Integer> inDegree, int[][] pairs) {
27        for (int u : graph.keySet()) {
28            if (outDegree.get(u) - inDegree.getOrDefault(u, 0) == 1) {
29                return u;
30            }
31        }
32        return pairs[0][0];
33    }
34
35    private void euler(Map<Integer, Stack<Integer>> graph, int u, List<List<Integer>> ans) {
36        Stack<Integer> stack = graph.get(u);
37        while (!stack.isEmpty()) {
38            int v = stack.pop();
39            euler(graph, v, ans);
40            ans.add(Arrays.asList(u, v));
41        }
42    }
43}

JavaScript Solution

1
2javascript
3class Solution {
4    validArrangement(pairs) {
5        let ans = [];
6        let graph = new Map();
7        let outDegree = new Map();
8        let inDegree = new Map();
9
10        for (let pair of pairs) {
11            let start = pair[0];
12            let end = pair[1];
13            if (!graph.has(start)) {
14                graph.set(start, []);
15            }
16            graph.get(start).push(end);
17            outDegree.set(start, (outDegree.get(start) || 0) + 1);
18            inDegree.set(end, (inDegree.get(end) || 0) + 1);
19        }
20
21        let startNode = this.getStartNode(graph, outDegree, inDegree, pairs);
22        this.euler(graph, startNode, ans);
23        ans.reverse();
24        return ans;
25    }
26
27    getStartNode(graph, outDegree, inDegree, pairs) {
28        for (let u of graph.keys()) {
29            if ((outDegree.get(u) || 0) - (inDegree.get(u) || 0) == 1) {
30                return u;
31            }
32        }
33        return pairs[0][0];
34    }
35
36    euler(graph, u, ans) {
37        while (graph.get(u).length > 0) {
38            let v = graph.get(u).pop();
39            this.euler(graph, v, ans);
40            ans.push([u, v]);
41        }
42    }
43}

C++ Solution

1
2cpp
3#include <unordered_map>
4#include <vector>
5#include <stack>
6#include <algorithm>
7
8using namespace std;
9
10class Solution {
11 public:
12  vector<vector<int>> validArrangement(vector<vector<int>>& pairs) {
13    vector<vector<int>> ans;
14    unordered_map<int, stack<int>> graph;
15    unordered_map<int, int> outDegree;
16    unordered_map<int, int> inDegree;
17
18    for (const vector<int>& pair : pairs) {
19      const int start = pair[0];
20      const int end = pair[1];
21      graph[start].push(end);
22      ++outDegree[start];
23      ++inDegree[end];
24    }
25
26    const int startNode = getStartNode(graph, outDegree, inDegree, pairs);
27    euler(graph, startNode, ans);
28    reverse(begin(ans), end(ans));
29    return ans;
30  }
31
32 private:
33  int getStartNode(const unordered_map<int, stack<int>>& graph,
34                   unordered_map<int, int>& outDegree,
35                   unordered_map<int, int>& inDegree,
36                   const vector<vector<int>>& pairs) {
37    for (const auto& [u, _] : graph)
38      if (outDegree[u] - inDegree[u] == 1)
39        return u;
40    return pairs[0][0];  // Arbitrarily choose a node
41  }
42
43  void euler(unordered_map<int, stack<int>>& graph, int u,
44             vector<vector<int>>& ans) {
45    auto& stack = graph[u];
46    while (!stack.empty()) {
47      const int v = stack.top();
48      stack.pop();
49      euler(graph, v, ans);
50      ans.push_back({u, v});
51    }
52  }
53};

C# Solution

1
2csharp
3using System;
4using System.Collections.Generic;
5
6public class Solution {
7    public IList<IList<int>> ValidArrangement(int[][] pairs) {
8        List<IList<int>> ans = new List<IList<int>>();
9        Dictionary<int, Stack<int>> graph = new Dictionary<int, Stack<int>>();
10        Dictionary<int, int> outDegree = new Dictionary<int, int>();
11        Dictionary<int, int> inDegree = new Dictionary<int, int>();
12
13        foreach (int[] pair in pairs) {
14            int start = pair[0];
15            int end = pair[1];
16            if (!graph.ContainsKey(start)) {
17                graph[start] = new Stack<int>();
18            }
19            graph[start].Push(end);
20            outDegree[start] = outDegree.GetValueOrDefault(start, 0) + 1;
21            inDegree[end] = inDegree.GetValueOrDefault(end, 0) + 1;
22        }
23
24        int startNode = GetStartNode(graph, outDegree, inDegree, pairs);
25        Euler(graph, startNode, ans);
26        ans.Reverse();
27        return ans;
28    }
29
30    private int GetStartNode(Dictionary<int, Stack<int>> graph, Dictionary<int, int> outDegree, Dictionary<int, int> inDegree, int[][] pairs) {
31        foreach (int u in graph.Keys) {
32            if (outDegree[u] - inDegree.GetValueOrDefault(u, 0) == 1) {
33                return u;
34            }
35        }
36        return pairs[0][0];
37    }
38
39    private void Euler(Dictionary<int, Stack<int>> graph, int u, List<IList<int>> ans) {
40        Stack<int> stack = graph[u];
41        while (stack.Count > 0) {
42            int v = stack.Pop();
43            Euler(graph, v, ans);
44            ans.Add(new int[] {u, v});
45        }
46    }
47}

In this article, we have implemented the validArrangement function using Hierholzer's algorithm for the following languages: Python, Java, JavaScript, C++, and C#. This function takes a list of directed node pairs called pairs and returns the correct arrangement of the edges. We created the directed graph using the given node pairs and applied Hierholzer's algorithm to form the valid arrangement.

Solution Implementation