Vik's blog

Help with an interesting problem? Looks straightforward but I failed to do it today during online assessment.
By Vik, history, 4 years ago, In English

Problem

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!

  • Vote: I like it
  • -25
  • Vote: I do not like it

Comments Comments (4)
| Write comment?
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

You can use graph to solve this problem, put an edge between each element of each pair .

→ Reply
  • »
    »
    4 years ago, # ^ |
      Vote: I like it 0 Vote: I do not like it

    How will you do it in O(n)?

    → Reply
    • »
      »
      »
      4 years ago, # ^ |
        Vote: I like it 0 Vote: I do not like it

      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.

      → Reply
»
4 years ago, # |
  Vote: I like it 0 Vote: I do not like it

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.

→ Reply