John and Fences – HackerRank Solution

In this post, we will solve John and Fences HackerRank Solution. This problem (John and Fences) is a part of HackerRank Functional Programming series.

Task

John’s house has bizarre fencing. There are N fences. Though the contiguous fences have the constant width of 1 unit but their height varies. Height of these fences is represented by array H = [h₁, h₂… h_N].John’s house has bizarre fencing. There are N fences. Though the contiguous fences have the constant width of 1 unit but their height varies. Height of these fences is represented by array H = [h₁, h₂… h_N].

John loves his fences but has to finally bow down to his wife’s repeated requests of replacing them with the regular fences. Before taking them down, John wants to keep some part of the fences as souvenir. He decides to carve out the largest rectangular area possible where the largest rectangle can be made of a number of contiguous fence. Note that sides of the rectangle should be parallel to X and Y axis.

Let’s say there are 6 fences, and their height is, H = [2, 5, 7, 4, 1, 8]. Then they can be represented as

                   __
8         __      |  |
7        |  |     |  |
6      __|  |     |  |
5     |  |  |__   |  |
4     |  |  |  |  |  |
3   __|  |  |  |  |  |
2  |  |  |  |  |__|  |
1  |__|__|__|__|__|__|
    h1 h2 h3 h4 h5 h6

Some possible carvings are as follow:

• If we carve rectangle from h1, h2 and h3 then we can get the max area of 2×3 = 6 units.
• If we carve rectangle from h3, h4, h5 and h6, then max area is 4×1 = 4 units.
• If we carve rectangle from h2, h3 and h4, then max area is 4×3 = 12, which is also the most optimal solution for this case.

Input

First line will contain an integer N denoting the number of fences. It will be followed by a line containing N space separated integers, h₁ h₂ … h_N, which represents the height of each fence.

Output

Print the maximum area of rectangle which can be carved out.

Constraints

• 1 ≤ N ≤ 10⁵
• 1 ≤ h_i ≤ 10⁴

Sample Input

6
2 5 7 4 1 8

Sample Output

12

Explanation

John can carve a rectangle of height 4 from fence #2, #3 and #4, whose respective heights are 5, 7 and 4. So this will lead to a rectangle of area 3×4 = 12 units.

Solution – John and Fences – HackerRank Solution

Scala

import java.util.Scanner

import scala.collection.immutable.TreeMap

object Solution {
  def main(args: Array[String]): Unit = {
    val sc = new Scanner(System.in)

    val n = sc.nextInt
    val h = (0 until n).map(_ => sc.nextInt)

    sc.close()

    case class Fence(height: Int, pos: Int)

    val fences = h.indices.map(i => Fence(h(i), i)).sortBy(_.height).toList

    case class Accumulator(tree: TreeMap[Int, Int], bestSquare: Int)
    println(
      fences.foldLeft(Accumulator(TreeMap(0 -> n), 0))((acc, x) => {
        val (left, right) = acc.tree.rangeTo(x.pos).last
        Accumulator(acc.tree - left + (left -> x.pos) + (x.pos + 1 -> right), math.max(acc.bestSquare, (right - left) * x.height))
      }).bestSquare
    )
  }
}

Note: This problem (John and Fences) is generated by HackerRank but the solution is provided by CodingBroz. This tutorial is only for Educational and Learning purpose.