2097. Valid Arrangement of Pairs Hard

1/**
2 * [2097] Valid Arrangement of Pairs
3 *
4 * 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.
5 * Return any valid arrangement of pairs.
6 * Note: The inputs will be generated such that there exists a valid arrangement of pairs.
7 *  
8 * Example 1:
9 * 
10 * Input: pairs = [[5,1],[4,5],[11,9],[9,4]]
11 * Output: [[11,9],[9,4],[4,5],[5,1]]
12 * Explanation:
13 * This is a valid arrangement since endi-1 always equals starti.
14 * end0 = 9 == 9 = start1 
15 * end1 = 4 == 4 = start2
16 * end2 = 5 == 5 = start3
17 * 
18 * Example 2:
19 * 
20 * Input: pairs = [[1,3],[3,2],[2,1]]
21 * Output: [[1,3],[3,2],[2,1]]
22 * Explanation:
23 * This is a valid arrangement since endi-1 always equals starti.
24 * end0 = 3 == 3 = start1
25 * end1 = 2 == 2 = start2
26 * The arrangements [[2,1],[1,3],[3,2]] and [[3,2],[2,1],[1,3]] are also valid.
27 * 
28 * Example 3:
29 * 
30 * Input: pairs = [[1,2],[1,3],[2,1]]
31 * Output: [[1,2],[2,1],[1,3]]
32 * Explanation:
33 * This is a valid arrangement since endi-1 always equals starti.
34 * end0 = 2 == 2 = start1
35 * end1 = 1 == 1 = start2
36 * 
37 *  
38 * Constraints:
39 * 
40 * 	1 <= pairs.length <= 10^5
41 * 	pairs[i].length == 2
42 * 	0 <= starti, endi <= 10^9
43 * 	starti != endi
44 * 	No two pairs are exactly the same.
45 * 	There exists a valid arrangement of pairs.
46 * 
47 */
48pub struct Solution {}
49
50// problem: https://leetcode.com/problems/valid-arrangement-of-pairs/
51// discuss: https://leetcode.com/problems/valid-arrangement-of-pairs/discuss/?currentPage=1&orderBy=most_votes&query=
52
53// submission codes start here
54
55impl Solution {
56    pub fn valid_arrangement(pairs: Vec<Vec<i32>>) -> Vec<Vec<i32>> {
57        vec![]
58    }
59}
60
61// submission codes end
62
63#[cfg(test)]
64mod tests {
65    use super::*;
66
67    #[test]
68    fn test_2097() {
69    }
70}
71