package leetcode;

import java.util.ArrayList;
import java.util.Arrays;
import java.util.HashMap;
import java.util.HashSet;
import java.util.List;
import java.util.Map;
import java.util.Set;

/**
 * https://leetcode.com/problems/restore-the-array-from-adjacent-pairs/
 */
public class Problem1743 {
    public int[] restoreArray(int[][] adjacentPairs) {
        Map<Integer, List<Integer>> pairs = new HashMap<>();
        Set<Integer> set = new HashSet<>();
        for (int[] pair : adjacentPairs) {
            pairs.putIfAbsent(pair[0], new ArrayList<>());
            pairs.get(pair[0]).add(pair[1]);
            pairs.putIfAbsent(pair[1], new ArrayList<>());
            pairs.getOrDefault(pair[1], new ArrayList<>()).add(pair[0]);
            set.add(pair[0]);
            set.add(pair[1]);
        }
        int first = 0;
        for (Map.Entry<Integer, List<Integer>> entry : pairs.entrySet()) {
            if (entry.getValue().size() == 1) {
                first = entry.getKey();
                break;
            }
        }
        int[] answer = new int[set.size()];
        answer[0] = first;
        Set<Integer> previous = new HashSet<>();
        previous.add(first);
        for (int i = 1; i < answer.length; i++) {
            int next = 0;
            for (int adj : pairs.get(answer[i - 1])) {
                if (!previous.contains(adj)) {
                    next = adj;
                    break;
                }
            }
            previous.add(next);
            answer[i] = next;
        }
        return answer;
    }

    public static void main(String[] args) {
        Problem1743 prob = new Problem1743();
        System.out.println(Arrays.toString(prob.restoreArray(new int[][]{
            {2,1},{3,4},{3,2}
        }))); // [1,2,3,4]
        System.out.println(Arrays.toString(prob.restoreArray(new int[][]{
            {4,-2},{1,4},{-3,1}
        }))); // [-2,4,1,-3]
        System.out.println(Arrays.toString(prob.restoreArray(new int[][]{
            {100000,-100000}
        }))); // [100000,-100000]
    }
}

@@ -44,33 +44,8 @@
 st;%0A
-import java.util.Arrays;%0A
 impo
@@ -314,32 +314,55 @@
 djacentPairs) %7B%0A
+        int first = 0;%0A
         Map%3CInte
@@ -410,52 +410,8 @@
 ();%0A
-        Set%3CInteger%3E set = new HashSet%3C%3E();%0A
     
@@ -697,92 +697,9 @@
     
-    set.add(pair%5B0%5D);%0A            set.add(pair%5B1%5D);%0A        %7D%0A        int first = 0;
+%7D
 %0A   
@@ -940,18 +940,32 @@
 int%5B
-set.size()
+adjacentPairs.length + 1
 %5D;%0A 
@@ -1441,508 +1441,7 @@
    %7D
-%0A%0A    public static void main(String%5B%5D args) %7B%0A        Problem1743 prob = new Problem1743();%0A        System.out.println(Arrays.toString(prob.restoreArray(new int%5B%5D%5B%5D%7B%0A            %7B2,1%7D,%7B3,4%7D,%7B3,2%7D%0A        %7D))); // %5B1,2,3,4%5D%0A        System.out.println(Arrays.toString(prob.restoreArray(new int%5B%5D%5B%5D%7B%0A            %7B4,-2%7D,%7B1,4%7D,%7B-3,1%7D%0A        %7D))); // %5B-2,4,1,-3%5D%0A        System.out.println(Arrays.toString(prob.restoreArray(new int%5B%5D%5B%5D%7B%0A            %7B100000,-100000%7D%0A        %7D))); // %5B100000,-100000%5D%0A    %7D
 %0A%7D%0A

Solve problem 1743