Scala solution with BFS identical to supplied Java solution gets TLE


  • 0
    S

    Here's my solution, with some tweaks to attempt to make it faster.
    I hit a Time Limit Exceeded. Does anyone have ideas on how to improve?

      def cutOffTree(forest: List[List[Int]]): Int = {
        case class SearchNode(node: Node, dist: Int)
        case class Tree(i: Int, j: Int, height: Int)
        case class Node(i: Int, j: Int)
        val diffs = Seq((-1,0), (1, 0), (0, -1), (0, 1))
    
        val visited = Array.ofDim[Boolean](forest.length, forest(0).length)
        val q = new mutable.Queue[SearchNode]()
        def shortestPath(source: Node, destination: Node): Int = {
          // Zero out visited
          for (i <- 0 until visited.length) {
            for (j <- 0 until visited(0).length) {
              visited(i)(j) = false
            }
          }
    
          // empty Queue
          while (q.nonEmpty) q.dequeue()
    
          println(s"Looking for sp from $source to $destination")
    
          visited(source.i)(source.j) = true
          q.enqueue(SearchNode(source, 0))
    
          var dist = -1
          var cont = true
    
          while (q.nonEmpty && cont) {
            val gNode = q.dequeue()
    
            val Node(i, j) = gNode.node
            val newDist = gNode.dist + 1
    
            diffs.foreach { case (di, dj) =>
              val ni = i + di
              val nj = j + dj
              if (
                inBounds(ni, visited.length) &&
                  inBounds(nj, visited(0).length) &&
                  !visited(ni)(nj) &&
                  forest(ni)(nj) != 0
              ) {
                visited(gNode.node.i)(gNode.node.j) = true
    
                if (ni == destination.i && nj == destination.j) {
                  dist = newDist
                  cont = false
                } else {
                  q.enqueue(SearchNode(Node(ni, nj), newDist))
                }
              }
            }
    
          }
    
          dist
        }
    
        val trees = mutable.ArrayBuffer[Tree]()
    
        for (i <- 0 until forest.length) {
          for (j <- 0 until forest(0).length) {
            if (forest(i)(j) > 1) trees.append(Tree(i, j, forest(i)(j)))
          }
        }
    
        val nodeOrder = trees.sortBy(_.height).map { case Tree(i, j, _) => Node(i, j) }
    
        var ans = 0
        var curr = Node(0, 0)
        var cont = true
        for (i <- 0 until nodeOrder.length if cont) {
          val next = nodeOrder(i)
          val sp = if (curr == next) 0 else shortestPath(curr, next)
          if (sp != -1) {
            ans += sp
            curr = next
          } else {
            ans = -1
            cont = false
          }
        }
    
        ans
      }
    

Log in to reply
 

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.