10.11.2023
1743. Restore the Array From Adjacent Pairs medium
blog post
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) }
}
}
}
}