LeetCode Entry

1743. Restore the Array From Adjacent Pairs

10.11.2023 medium 2023 kotlin

Restore an array from adjacent pairs

1743. Restore the Array From Adjacent Pairs medium blog post substack image.png

Join me on Telegram

https://t.me/leetcode_daily_unstoppable/399

Problem TLDR

Restore an array from adjacent pairs

Intuition

We can form an undirected graph and do a Depth-First Search

Complexity

  • Time complexity: \(O(n)\)

  • Space complexity: \(O(n)\)

Code


    fun restoreArray(adjacentPairs: Array<IntArray>): IntArray {
      val fromTo = mutableMapOf<Int, MutableList<Int>>()
      for ((from, to) in adjacentPairs) {
        fromTo.getOrPut(from) { mutableListOf() } += to
        fromTo.getOrPut(to) { mutableListOf() } += from
      }
      val visited = HashSet<Int>()
      with(ArrayDeque<Int>()) {
        add(fromTo.keys.first { fromTo[it]!!.size == 1 }!!)
        return IntArray(adjacentPairs.size + 1) {
          while (first() in visited) removeFirst()
          removeFirst().also {
            visited.add(it)
            fromTo[it]?.onEach { add(it) }
          }
        }
      }
    }