LeetCode Entry

332. Reconstruct Itinerary

14.09.2023 hard 2023 kotlin

Smallest lexical order path using all the tickets

332. Reconstruct Itinerary hard blog post substack image.png

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 node

  • Space 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()
    }