TLE error for correct Scala solution for largest rectangle for histogram

  • 0

    Following program executes fine and reasonably fast(~o(n)). However upon submitting, LeetCode shows TLE(Time Limit Exceeded) error without any further info such as what was expected time, what input it was testing and how much time the code too to execute. Any insights?

        def largestRectangleArea(heights: Array[Int]): Int = {
            def getArea(element: Int, leftSpan: Int, rightSpan: Int) = (leftSpan + rightSpan + 1) * element
            def max(area1: Int, area2: Int): Int = if (area1 > area2) area1 else area2
            def pivot(xs: Vector[Int], ps: Vector[Int], area: Int): Int = xs match {
                case Vector()=> area
              case x +: xs1 => pivot(xs1, x +: ps, max(area, getArea(x, ps.takeWhile(_ > x).length, xs1.takeWhile(_ > x).length)))
            pivot(heights.toVector, Vector(), 0)

Log in to reply

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