14.09.2023
332. Reconstruct Itinerary hard
blog post
Join me on Telegram
https://t.me/leetcode_daily_unstoppable/339
Problem TLDR
Smallest lexical order path using all the tickets
Intuition
We can build a graph, then do DFS in a lexical order, backtracking. First path with all tickets used will be the answer.
Approach
graph has directed nodes
sort nodes lists by strings comparison
current node is always the last in the path
Complexity
Time complexity:
O(x^n), where x—is an average edges count per nodeSpace complexity:
O(n)
Code
fun findItinerary(tickets: List<List<String>>): List<String> {
val fromTo = mutableMapOf<String, MutableList<Pair<Int, String>>>()
tickets.forEachIndexed { i, (from, to) ->
fromTo.getOrPut(from) { mutableListOf() } += i to to
}
for (list in fromTo.values) list.sortWith(compareBy { it.second })
val usedTickets = mutableSetOf<Int>()
var path = mutableListOf("JFK")
fun dfs(): List<String> =
if (usedTickets.size == tickets.size) path.toList()
else fromTo[path.last()]?.asSequence()?.map { (ind, next) ->
if (usedTickets.add(ind)) {
path.add(next)
dfs().also {
path.removeAt(path.lastIndex)
usedTickets.remove(ind)
}
} else emptyList()
}?.filter { it.isNotEmpty() }?.firstOrNull() ?: emptyList()
return dfs()
}