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 <= 105pairs[i].length == 20 <= starti, endi <= 109starti != endipairs.class Solution {
int n;
boolean found;
public int[][] validArrangement(int[][] pairs) {
n = pairs.length;
Map<Integer, List<Integer>> adj = new HashMap<>();
boolean[] vis = new boolean[n];
int[][] path = new int[n][2];
for (int i = 0; i < n; i++) {
adj.putIfAbsent(pairs[i][0], new ArrayList<>());
adj.get(pairs[i][0]).add(i);
}
// System.out.println(adj);
for (int i = 0; i < n; i++) {
vis[i] = true;
path[0] = pairs[i];
path = dfs(i, pairs, adj, vis, path, 1);
vis[i] = false;
if (found)
return path;
}
return path;
}
private int[][] dfs(int src, int[][] pairs,
Map<Integer, List<Integer>> adj,
boolean[] vis, int[][] path, int pathLen) {
if (pathLen == n) {
found = true;
return path;
}
for (int nbr : adj.getOrDefault(pairs[src][1], new ArrayList<>())) {
if (vis[nbr])
continue;
vis[nbr] = true;
path[pathLen] = pairs[nbr];
int[][] res = dfs(nbr, pairs, adj, vis, path, pathLen + 1);
if (found)
return res;
vis[nbr] = false;
}
return path;
}
}