Discussion on John and Fences Challenge

Sort by

recency

|

10 Discussions

|

7 months ago+ 0 comments

scala:

import scala.collection.mutable.Stack
import scala.io.StdIn.readLine

object Solution {
  private def carve(heights: Seq[Int]): Int = {
    val extendedHeights = heights :+ 0
    val stack = Stack[Int]()
    var maxArea = 0
    for (i <- extendedHeights.indices) {
      while (stack.nonEmpty && extendedHeights(i) < extendedHeights(stack.top)) {
        val height = extendedHeights(stack.pop())
        val width = if (stack.isEmpty) i else (i - stack.top - 1)
        maxArea = math.max(maxArea, height * width)
      }
      stack.push(i)
    }
    maxArea
  }

  def main(args: Array[String]): Unit = {
    readLine()
    val heights = readLine().trim.split(' ').map(_.toInt).toSeq
    println(carve(heights))
  }
}

3 years ago+ 0 comments

Is it availble for Fence Cleaning Atlanta website? I want to integrate it on my website.

4 years ago+ 1 comment

My solution i find by scala

4 years ago+ 0 comments

import java.io._ import scala.collection.mutable.ArrayBuffer import scala.math

object Solution { def main(args: Array[String]) { val rd = new BufferedReader(new InputStreamReader(System.in)) val N = rd.readLine().toInt val h = Array(0) ++ rd.readLine().split(' ').map(_.toInt) ++ Array(0) var l: ArrayBuffer[Int] = ArrayBuffer.fill(h.length)(-1) var r: ArrayBuffer[Int] = ArrayBuffer.fill(h.length)(-1) for (i <- 1 until h.length - 1) { var ll: Int = i - 1 if (h(ll) < h(i)) { l(i) = i } else { while (ll != -1 && h(ll) >= h(i)) { l(i) = ll if (ll == l(ll)) ll = ll - 1 else ll = l(ll) } } } for (i <- h.length - 2 to 1 by -1) { var rr: Int = i + 1 if (h(rr) < h(i)) { r(i) = i } else { while (rr != -1 && h(rr) >= h(i)) { r(i) = rr if (rr == r(rr)) rr = rr + 1 else rr = r(rr) } } } var ans = 0 for (i <- 1 until h.length - 1) { ans = math.max(ans, (r(i) - l(i) + 1) * h(i)) } println(ans) } }

4 years ago+ 0 comments

Got pretty close, think the algorithm is correct, I think I just need to make some optimizations to the stuff i'm caching / rechecking:

(let [line1 (read-line)]
    (let [fences (map read-string (clojure.string/split (read-line) #" "))]
        (println
            ((fn[x cache stopped-cache]
                (if (= x (count fences))
                    (apply max (map (fn[x] (x :valu)) (into cache stopped-cache)))
                    (let [fence (nth fences x)]
                        (recur (+ 1 x)
                            (conj (map (fn[x]
                                (let [m (min (x :mini) fence)
                                    newWidth (+ 1 (x :width))
                                    newValu (* newWidth m)]
                                    {:valu newValu :mini m :width newWidth}
                                )
                            ) cache) {:valu fence :mini fence :width 1})
                            (into stopped-cache cache)
                        )
                    )
                )
            ) 0 [{:valu 0 :mini Integer/MAX_VALUE :width 0 }] [])
        )
    )
)

6 years ago+ 1 comment

Did anyone make passing Scala solution? Mime timeouts on 5 to 10. I will try to port my solution to Haskell...

6 years ago+ 0 comments

yes, my approach is simply count the number of that bigger or equal to the i-th element for each i. It passes the testcases. But there is a more efficent approach for this problem by maintain a non-decreasing stack.

def largestRectangleArea(heights: Array[Int]): Int = {
  def f(l:List[Int], acc:Int):Int = l match {
    case Nil => acc
    case h::t => f(t, countlr(heights, h) * heights(h) max acc)
  }
  f(heights.indices.toList, 0)
}
def countlr(A:Array[Int], s:Int):Int = f(A,s)(s+1, 0) + g(A,s)(s-1, 0) + 1

def f(A:Array[Int], s:Int)(i:Int,cnt:Int):Int = if(i >= A.length) cnt else {
    if(A(i) >= A(s)) f(A,s)(i+1, cnt + 1) else cnt
}

def g(A:Array[Int], s:Int)(i:Int,cnt:Int):Int = if(i < 0) cnt else {
    if(A(i) >= A(s)) g(A,s)(i-1, cnt + 1) else cnt
}
    ```

Sort by

|

10 Discussions

|

Cookie support is required to access HackerRank

Please signup or login in order to view this challenge