{"id":7006,"date":"2022-07-25T23:00:00","date_gmt":"2022-07-25T17:30:00","guid":{"rendered":"https:\/\/www.codingbroz.com\/?p=7006"},"modified":"2022-07-13T19:05:32","modified_gmt":"2022-07-13T13:35:32","slug":"john-and-fences-hackerrank-solution","status":"publish","type":"post","link":"https:\/\/www.codingbroz.com\/john-and-fences-hackerrank-solution\/","title":{"rendered":"John and Fences &#8211; HackerRank Solution"},"content":{"rendered":"\n<p>In this post, we will solve <strong>John and Fences HackerRank Solution<\/strong>. This problem <strong>(John and Fences)<\/strong> is a part of <strong>HackerRank Functional Programming<\/strong> series.<\/p>\n\n\n\n<div id=\"ez-toc-container\" class=\"ez-toc-v2_0_65 ez-toc-wrap-left counter-hierarchy ez-toc-counter ez-toc-custom ez-toc-container-direction\">\n<label for=\"ez-toc-cssicon-toggle-item-66348df907a3b\" class=\"ez-toc-cssicon-toggle-label\"><label class=\"ez-toc-title\">Table of Contents<\/label>\n<span class=\"ez-toc-cssicon\"><span class=\"eztoc-hide\" style=\"display:none;\">Toggle<\/span><span class=\"ez-toc-icon-toggle-span\"><svg style=\"fill: #0090ff;color:#0090ff\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" class=\"list-377408\" width=\"20px\" height=\"20px\" viewBox=\"0 0 24 24\" fill=\"none\"><path d=\"M6 6H4v2h2V6zm14 0H8v2h12V6zM4 11h2v2H4v-2zm16 0H8v2h12v-2zM4 16h2v2H4v-2zm16 0H8v2h12v-2z\" fill=\"currentColor\"><\/path><\/svg><svg style=\"fill: #0090ff;color:#0090ff\" class=\"arrow-unsorted-368013\" xmlns=\"http:\/\/www.w3.org\/2000\/svg\" width=\"10px\" height=\"10px\" viewBox=\"0 0 24 24\" version=\"1.2\" baseProfile=\"tiny\"><path d=\"M18.2 9.3l-6.2-6.3-6.2 6.3c-.2.2-.3.4-.3.7s.1.5.3.7c.2.2.4.3.7.3h11c.3 0 .5-.1.7-.3.2-.2.3-.5.3-.7s-.1-.5-.3-.7zM5.8 14.7l6.2 6.3 6.2-6.3c.2-.2.3-.5.3-.7s-.1-.5-.3-.7c-.2-.2-.4-.3-.7-.3h-11c-.3 0-.5.1-.7.3-.2.2-.3.5-.3.7s.1.5.3.7z\"\/><\/svg><\/span><\/span><\/label><input type=\"checkbox\"  id=\"ez-toc-cssicon-toggle-item-66348df907a3b\" checked \/><nav><ul class='ez-toc-list ez-toc-list-level-1 ' ><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-1\" href=\"https:\/\/www.codingbroz.com\/john-and-fences-hackerrank-solution\/#Task\" title=\"Task\">Task<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-2\" href=\"https:\/\/www.codingbroz.com\/john-and-fences-hackerrank-solution\/#Input\" title=\"Input\">Input<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-3\" href=\"https:\/\/www.codingbroz.com\/john-and-fences-hackerrank-solution\/#Output\" title=\"Output\">Output<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-4\" href=\"https:\/\/www.codingbroz.com\/john-and-fences-hackerrank-solution\/#Constraints\" title=\"Constraints\">Constraints<\/a><\/li><li class='ez-toc-page-1 ez-toc-heading-level-2'><a class=\"ez-toc-link ez-toc-heading-5\" href=\"https:\/\/www.codingbroz.com\/john-and-fences-hackerrank-solution\/#Solution_%E2%80%93_John_and_Fences_%E2%80%93_HackerRank_Solution\" title=\"Solution &#8211; John and Fences &#8211; HackerRank Solution\">Solution &#8211; John and Fences &#8211; HackerRank Solution<\/a><\/li><\/ul><\/nav><\/div>\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Task\"><\/span><strong>Task<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>John&#8217;s house has bizarre fencing. There are\u00a0<em>N<\/em>\u00a0fences. Though the contiguous fences have the constant width of 1 unit but their height varies. Height of these fences is represented by array\u00a0<em>H = [h<sub>1<\/sub>, h<sub>2<\/sub>&#8230; h<sub>N<\/sub>]<\/em>.John&#8217;s house has bizarre fencing. There are\u00a0<em>N<\/em>\u00a0fences. Though the contiguous fences have the constant width of 1 unit but their height varies. Height of these fences is represented by array\u00a0<em>H = [h<sub>1<\/sub>, h<sub>2<\/sub>&#8230; h<sub>N<\/sub>]<\/em>.<\/p>\n\n\n\n<p>John loves his fences but has to finally bow down to his wife&#8217;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&nbsp;<em>X<\/em>&nbsp;and&nbsp;<em>Y<\/em>&nbsp;axis.<\/p>\n\n\n\n<p>Let&#8217;s say there are 6 fences, and their height is,\u00a0<em>H<\/em>\u00a0=\u00a0<em>[2, 5, 7, 4, 1, 8]<\/em>. Then they can be represented as<\/p>\n\n\n\n<pre class=\"wp-block-code\"><code>                   __\r\n8         __      |  |\r\n7        |  |     |  |\r\n6      __|  |     |  |\r\n5     |  |  |__   |  |\r\n4     |  |  |  |  |  |\r\n3   __|  |  |  |  |  |\r\n2  |  |  |  |  |__|  |\r\n1  |__|__|__|__|__|__|\r\n    h1 h2 h3 h4 h5 h6<\/code><\/pre>\n\n\n\n<p class=\"has-ast-global-color-5-color has-ast-global-color-8-background-color has-text-color has-background\">Some possible carvings are as follow:<\/p>\n\n\n\n<ul><li>If we carve rectangle from\u00a0<em>h1, h2 and h3<\/em>\u00a0then we can get the max area of 2&#215;3 = 6 units.<\/li><li>If we carve rectangle from\u00a0<em>h3, h4, h5 and h6<\/em>, then max area is 4&#215;1 = 4 units.<\/li><li>If we carve rectangle from\u00a0<em>h2, h3 and h4<\/em>, then max area is 4&#215;3 = 12, which is also the most optimal solution for this case.<\/li><\/ul>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Input\"><\/span><strong>Input<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>First line will contain an integer\u00a0<em>N<\/em>\u00a0denoting the number of fences. It will be followed by a line containing\u00a0<em>N<\/em>\u00a0space separated integers,\u00a0<em>h<sub>1<\/sub>\u00a0h<sub>2<\/sub>\u00a0&#8230; h<sub>N<\/sub><\/em>, which represents the height of each fence.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Output\"><\/span><strong>Output<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>Print the maximum area of rectangle which can be carved out.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Constraints\"><\/span><strong>Constraints<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<ul><li>1 \u2264\u00a0<em>N<\/em>\u00a0\u2264 10<sup>5<\/sup><\/li><li>1 \u2264\u00a0<em>h<sub>i<\/sub><\/em>\u00a0\u2264 10<sup>4<\/sup><\/li><\/ul>\n\n\n\n<p><strong>Sample Input<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-ast-global-color-5-color has-ast-global-color-8-background-color has-text-color has-background\"><code>6\r\n2 5 7 4 1 8<\/code><\/pre>\n\n\n\n<p><strong>Sample Output<\/strong><\/p>\n\n\n\n<pre class=\"wp-block-code has-ast-global-color-5-color has-ast-global-color-8-background-color has-text-color has-background\"><code>12<\/code><\/pre>\n\n\n\n<p><strong>Explanation<\/strong><\/p>\n\n\n\n<p>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&#215;4 = 12 units.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Solution_%E2%80%93_John_and_Fences_%E2%80%93_HackerRank_Solution\"><\/span><strong>Solution &#8211; John and Fences &#8211; HackerRank Solution<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p><strong>Scala<\/strong><\/p>\n\n\n\n<pre class=\"EnlighterJSRAW\" data-enlighter-language=\"scala\" data-enlighter-theme=\"\" data-enlighter-highlight=\"\" data-enlighter-linenumbers=\"\" data-enlighter-lineoffset=\"\" data-enlighter-title=\"\" data-enlighter-group=\"\">import java.util.Scanner\n\nimport scala.collection.immutable.TreeMap\n\nobject Solution {\n  def main(args: Array[String]): Unit = {\n    val sc = new Scanner(System.in)\n\n    val n = sc.nextInt\n    val h = (0 until n).map(_ => sc.nextInt)\n\n    sc.close()\n\n    case class Fence(height: Int, pos: Int)\n\n    val fences = h.indices.map(i => Fence(h(i), i)).sortBy(_.height).toList\n\n    case class Accumulator(tree: TreeMap[Int, Int], bestSquare: Int)\n    println(\n      fences.foldLeft(Accumulator(TreeMap(0 -> n), 0))((acc, x) => {\n        val (left, right) = acc.tree.rangeTo(x.pos).last\n        Accumulator(acc.tree - left + (left -> x.pos) + (x.pos + 1 -> right), math.max(acc.bestSquare, (right - left) * x.height))\n      }).bestSquare\n    )\n  }\n}\n<\/pre>\n\n\n\n<p><strong>Note: <\/strong>This problem <strong>(<a href=\"https:\/\/www.hackerrank.com\/challenges\/john-and-fences\/problem\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">John and Fences<\/a>)<\/strong> is generated by <strong><a href=\"https:\/\/www.hackerrank.com\/\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">HackerRank<\/a><\/strong> but the solution is provided by <strong><a href=\"https:\/\/www.codingbroz.com\/\">CodingBroz<\/a><\/strong>. This tutorial is only for <strong>Educational<\/strong> and <strong>Learning<\/strong> purpose.<\/p>\n","protected":false},"excerpt":{"rendered":"<p>In this post, we will solve John and Fences HackerRank Solution. This problem (John and Fences) is a part of HackerRank Functional Programming series.<\/p>\n","protected":false},"author":2,"featured_media":0,"comment_status":"open","ping_status":"closed","sticky":false,"template":"","format":"standard","meta":{"site-sidebar-layout":"default","site-content-layout":"","ast-site-content-layout":"","site-content-style":"default","site-sidebar-style":"default","ast-global-header-display":"","ast-banner-title-visibility":"","ast-main-header-display":"","ast-hfb-above-header-display":"","ast-hfb-below-header-display":"","ast-hfb-mobile-header-display":"","site-post-title":"","ast-breadcrumbs-content":"","ast-featured-img":"","footer-sml-layout":"","theme-transparent-header-meta":"","adv-header-id-meta":"","stick-header-meta":"","header-above-stick-meta":"","header-main-stick-meta":"","header-below-stick-meta":"","astra-migrate-meta-layouts":"default","ast-page-background-enabled":"default","ast-page-background-meta":{"desktop":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"ast-content-background-meta":{"desktop":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"tablet":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""},"mobile":{"background-color":"var(--ast-global-color-5)","background-image":"","background-repeat":"repeat","background-position":"center center","background-size":"auto","background-attachment":"scroll","background-type":"","background-media":"","overlay-type":"","overlay-color":"","overlay-gradient":""}},"_jetpack_memberships_contains_paid_content":false,"footnotes":""},"categories":[9,684],"tags":[692],"jetpack_sharing_enabled":true,"jetpack_featured_media_url":"","jetpack-related-posts":[],"_links":{"self":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/7006"}],"collection":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts"}],"about":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/types\/post"}],"author":[{"embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/users\/2"}],"replies":[{"embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/comments?post=7006"}],"version-history":[{"count":3,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/7006\/revisions"}],"predecessor-version":[{"id":7010,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/7006\/revisions\/7010"}],"wp:attachment":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/media?parent=7006"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/categories?post=7006"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/tags?post=7006"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}