LeetCode 2097. Valid Arrangement of Pairs

原题链接在这里：https://leetcode.com/problems/valid-arrangement-of-pairs/description/

题目：

You are given a 0-indexed 2D integer array pairs where pairs[i] = [starti, endi]. An arrangement of pairs is valid if for every index i where 1 <= i < pairs.length, we have endi-1 == starti.

Return any valid arrangement of pairs.

Note: The inputs will be generated such that there exists a valid arrangement of pairs.

Example 1:

Input: pairs = [[5,1],[4,5],[11,9],[9,4]]
Output: [[11,9],[9,4],[4,5],[5,1]]
Explanation:
This is a valid arrangement since endi-1 always equals starti.
end0 = 9 == 9 = start1 
end1 = 4 == 4 = start2
end2 = 5 == 5 = start3

Example 2:

Input: pairs = [[1,3],[3,2],[2,1]]
Output: [[1,3],[3,2],[2,1]]
Explanation:
This is a valid arrangement since endi-1 always equals starti.
end0 = 3 == 3 = start1
end1 = 2 == 2 = start2
The arrangements [[2,1],[1,3],[3,2]] and [[3,2],[2,1],[1,3]] are also valid.

Example 3:

Input: pairs = [[1,2],[1,3],[2,1]]
Output: [[1,2],[2,1],[1,3]]
Explanation:
This is a valid arrangement since endi-1 always equals starti.
end0 = 2 == 2 = start1
end1 = 1 == 1 = start2

Constraints:

• 1 <= pairs.length <= 105
• pairs[i].length == 2
• 0 <= starti, endi <= 109
• starti != endi
• No two pairs are exactly the same.
• There exists a valid arrangement of pairs.

题解：

For each pair, can view it as an edge in graph. We would like to traverse all the edges once and find the path. That is Eulerian Path.

Eulerian path exist when all the outDegree = inDegree for all the nodes or two nodes exceptions the head and tail.

Since here we are guaranteed that there is a eulerian path, we skip checking the existance.

To tranverse, we recursively DFS from the start node, but when hitting the last node, there could be cases that there are edges that are not traversed yet, thus we need to backtracking to that state and traverse the rest.

After traversing all the nodes, add the last edge to the result.

Time Complexity: O(v + e). e = pairs.length. n is the number of nodes in graph.

Space: O(v + e).

AC Java:

 1 class Solution {
 2     public int[][] validArrangement(int[][] pairs) {
 3         HashMap<Integer, Stack<Integer>> graph = new HashMap<>();
 4         HashMap<Integer, Integer> out = new HashMap<>();
 5         for(int[] p : pairs){
 6             int u = p[0];
 7             int v = p[1];
 8             graph.computeIfAbsent(u, x -> new Stack<>()).push(v);
 9             out.put(u, out.getOrDefault(u, 0) + 1);
10             out.put(v, out.getOrDefault(v, 0) - 1);
11         }
12 
13         int start = -1;
14         for(Map.Entry<Integer, Integer> e : out.entrySet()){
15             if(e.getValue() == 1){
16                 start = e.getKey();
17                 break;
18             }
19         }
20 
21         if(start == -1){
22             start = pairs[0][0];
23         }
24 
25         LinkedList<int[]> res = new LinkedList<>();
26         eular(graph, start, res);
27         return res.toArray(new int[res.size()][2]);
28     }
29 
30     private void eular(HashMap<Integer, Stack<Integer>> graph, int start, LinkedList<int[]> res){
31         Stack<Integer> nexts = graph.getOrDefault(start, null);
32         while(nexts != null && !nexts.isEmpty()){
33             int next = nexts.pop();
34             eular(graph, next, res);
35             res.addFirst(new int[]{start, next});
36         }
37     } 
38 }