Vik's blog

By Vik, history, 3 years ago,

Constraints:

Size of the array: [1 10^5]

Element: 1 <= a[i] <= 10^6

Brute force won't work because of the constraints. I tried thinking of various ways but all were convoluted. I feel there is an easier way to think about it but I am missing some observation.

Any help would be highly appreciated.

Thanks!

• -25

| Write comment?
 » 3 years ago, # |   0 You can use graph to solve this problem, put an edge between each element of each pair .
•  » » 3 years ago, # ^ |   0 How will you do it in O(n)?
•  » » » 3 years ago, # ^ |   0 Draw an undirected edge between every element in the pair. You know that the ends of the array must have degree 1, as they are only adjacent to 1 element. Just find any node with degree 1, run a dfs from there, and return the order in which you visited the elements in the dfs. One other thing to note is that you can "coordinate-compress" the values in the array, so your runtime is $O(N)$, not $O(N+A)$, where $A$ is the maximum value of an array element.
 » 3 years ago, # |   0 Since all the values are different we can construct a graph from the pairs. Suppose we have pair [a, b] , lets make an edge a — b. After we built the graph we can find the vertex with degree of 1 and make a simple dfs to print the array.