{"id":7342,"date":"2022-08-12T23:00:00","date_gmt":"2022-08-12T17:30:00","guid":{"rendered":"https:\/\/www.codingbroz.com\/?p=7342"},"modified":"2022-08-07T14:33:49","modified_gmt":"2022-08-07T09:03:49","slug":"stock-prediction-hackerrank-solution","status":"publish","type":"post","link":"https:\/\/www.codingbroz.com\/stock-prediction-hackerrank-solution\/","title":{"rendered":"Stock Prediction &#8211; HackerRank Solution"},"content":{"rendered":"\n<p>In this post, we will solve <strong>Stock Prediction HackerRank Solution<\/strong>. This problem <strong>(Stock Prediction)<\/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-662d8ec17bfd1\" 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-662d8ec17bfd1\" 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\/stock-prediction-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\/stock-prediction-hackerrank-solution\/#Input_Format\" title=\"Input Format\">Input Format<\/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\/stock-prediction-hackerrank-solution\/#Output_Format\" title=\"Output Format\">Output Format<\/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\/stock-prediction-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\/stock-prediction-hackerrank-solution\/#Solution_%E2%80%93_Stock_Prediction_%E2%80%93_HackerRank_Solution\" title=\"Solution &#8211; Stock Prediction &#8211; HackerRank Solution\">Solution &#8211; Stock Prediction &#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>George is very concerned about the stock options his company has granted him, because the company&#8217;s stock price has fluctuated unpredictably and has often failed to meet expectations. With this in mind, George has decided to sell his options. Before doing so, he would like to perform a series of calculations.<\/p>\n\n\n\n<p>Stock price history is presented as an array of positive integers,\u00a0<strong><em>A<\/em> = {<em>a<\/em><sub>0<\/sub>, <em>a<\/em><sub>1<\/sub>, . . . , <em>a<\/em><sub>n-1<\/sub>}<\/strong>, which represents the average price per day of that stock. For a given day\u00a0<strong><em>d<\/em> (0 &lt;= <em>d<\/em> &lt; <em>n<\/em>)<\/strong>\u00a0and margin\u00a0<em><strong>M<\/strong><\/em>, George needs to find the longest subarray containing the day&#8217;s entry as a minimum,\u00a0<strong><em>a<\/em><sub><em>d<\/em><\/sub><\/strong>, and all other entries not exceeding\u00a0<strong><em>a<\/em><sub><em>d<\/em><\/sub> + M<\/strong>.<\/p>\n\n\n\n<p>That is, he has to find the longest subarray,\u00a0<strong><em>A<\/em>[<em>l<\/em>, <em>r<\/em>] = {<em>a<\/em><sub>l<\/sub>, <em>a<\/em><sub>l+1<\/sub>, . . . , <em>a<\/em><sub>r<\/sub>}<\/strong>, such that<\/p>\n\n\n\n<ul><li><strong>0 &lt;= <em>l<\/em> &lt;= <em>d<\/em> &lt;= <em>r<\/em> &lt; <em>n<\/em><\/strong><\/li><li><strong><em>a<\/em><sub>d<\/sub> = <em>minimum<\/em>{<em>A<\/em>[<em>l<\/em>, <em>r<\/em>]}<\/strong><\/li><li><strong><em>i<\/em> \u2208[<em>l<\/em>, <em>r<\/em>], <em>a<\/em><sub>d<\/sub> &lt;= <em>a<\/em><sub>i<\/sub> &lt;= <em>a<\/em><sub>d<\/sub> + M<\/strong><\/li><\/ul>\n\n\n\n<p>George asks you to help him solve this problem.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Input_Format\"><\/span><strong>Input Format<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>The first list contains an integer\u00a0<em><strong>n<\/strong><\/em>\u00a0which represents the length of the array\u00a0<em><strong>A<\/strong><\/em>. The second line contains\u00a0<em><strong>n<\/strong><\/em>\u00a0space-separated integers,\u00a0<strong><em>a<\/em><sub>0<\/sub>, <em>a<\/em><sub>1<\/sub>, . . . , <em>a<sub>n-1<\/sub><\/em><\/strong>, which represent the element of array\u00a0<em><strong>A<\/strong><\/em>. The next line contains the number of queries\u00a0<em><strong>Q<\/strong><\/em>. Each of the subsequent\u00a0<em><strong>Q<\/strong><\/em>\u00a0lines contain two integers\u00a0<em><strong>d<\/strong><\/em>\u00a0and\u00a0<em><strong>M<\/strong><\/em>\u00a0which represent the index of the element, which should be minimal and be included in subarray, and margin, respectively.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Output_Format\"><\/span><strong>Output Format<\/strong><span class=\"ez-toc-section-end\"><\/span><\/h2>\n\n\n\n<p>For each query output the length of the longest subarray with the required properties.<\/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><strong>1 &lt;= <em>n<\/em> &lt;= 5 x 10<sup>4<\/sup><\/strong><\/li><li><strong>1 &lt;= <em>A<\/em>[<em>i<\/em>] &lt;= 10<sup>9<\/sup>, 0 &lt;= <em>i<\/em> &lt; <em>n<\/em><\/strong><\/li><li><strong>1 &lt;= <em>Q<\/em> &lt;= 10<sup>5<\/sup><\/strong><\/li><li><strong>0 &lt;= <em>d<\/em> &lt; <em>n<\/em><\/strong><\/li><li><strong>0 &lt;= <em>M<\/em> &lt;= 10<sup>9<\/sup><\/strong><\/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>5\r\n3 5 2 6 1\r\n2\r\n0 2\r\n2 3<\/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>2\r\n3<\/code><\/pre>\n\n\n\n<p><strong>Explanation<\/strong><\/p>\n\n\n\n<p><em>Query #1:<\/em>\u00a0The first element,\u00a0<strong><em>a<\/em><sub>0<\/sub> = 3<\/strong>, should be included in the subarray. Since\u00a0<strong><em>a<\/em><sub>1<\/sub> = 5<\/strong>\u00a0is not less than\u00a0<strong>3<\/strong> and does not cross the margin (<strong>3 + 2 = 5<\/strong>), it can be included. The third element,\u00a0<strong><em>a<\/em><sub>2<\/sub> = 2<\/strong>, is less than the first element, so it cannot be included. To that end, the answer here is 2, as the longest subarray will be\u00a0<strong><em>A<\/em>[0, 1]<\/strong>.<\/p>\n\n\n\n<p><em>Query #2:<\/em>\u00a0Here\u00a0<strong><em>d<\/em> = 2<\/strong>\u00a0and\u00a0<strong><em>a<\/em><sub>d<\/sub> = 2<\/strong>. The next element,\u00a0<strong><em>a<\/em><sub>3<\/sub> = 6<\/strong>, is excluded because it is greater than the margin,\u00a0<strong>2 + 3 = 5<\/strong>. All of the previous elements will be included, as they are within the allowed range\u00a0<strong>[2, 5]<\/strong>. To that end, the longest subarray will be\u00a0<strong><em>A<\/em>[0, 2]<\/strong>\u00a0and have a length of 3.<\/p>\n\n\n\n<h2 class=\"wp-block-heading\"><span class=\"ez-toc-section\" id=\"Solution_%E2%80%93_Stock_Prediction_%E2%80%93_HackerRank_Solution\"><\/span><strong>Solution &#8211; Stock Prediction &#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.io._\nimport java.util.StringTokenizer\n\nimport scala.collection.mutable\n\nclass FastReader() {\n  val br: BufferedReader = new BufferedReader(new InputStreamReader(System.in))\n  var st: StringTokenizer = _\n\n  def nextInt: Int = next.toInt\n\n  def nextLong: Long = next.toLong\n\n  def next: String = {\n    while (st == null || !st.hasMoreElements)\n      try\n        st = new StringTokenizer(br.readLine)\n      catch {\n        case e: IOException =>\n          e.printStackTrace()\n      }\n    st.nextToken\n  }\n\n  def nextDouble: Double = next.toDouble\n\n  def nextLine: String = {\n    var str = \"\"\n    try\n      str = br.readLine\n    catch {\n      case e: IOException =>\n        e.printStackTrace()\n    }\n    str\n  }\n}\n\nobject Solution {\n  def main(args: Array[String]): Unit = {\n    val sc = new FastReader\n\n    val n = sc.nextInt\n    val arr = (0 until n).map(_ => sc.nextInt)\n\n    case class Query(index: Int, d: Int, up: Int)\n    val m = sc.nextInt\n    val queries = (0 until m).map(i => {\n      val d = sc.nextInt\n      Query(i, d, arr(d) + sc.nextInt)\n    })\n\n    def updateMap(map: mutable.Map[Int, Int], left: Int, right: Int): Unit =\n      if (left &lt;= right)\n        map += (left -> right)\n      else\n        map -= left\n\n    case class Item(value: Int, positions: IndexedSeq[Int]) extends Ordered[Item] {\n      override def compare(that: Item): Int = this.value.compareTo(that.value)\n    }\n\n    val tempMap = mutable.Map[Int, List[Int]]()\n    arr.indices.foreach(i => {\n      val v = arr(i)\n      tempMap += v -> (i :: tempMap.getOrElse(v, Nil))\n    })\n\n    val sortedArray = tempMap.map { case (v, list) => Item(v, list.toIndexedSeq) }.toIndexedSeq.sorted\n\n    val minBoundMap: mutable.TreeMap[Int, Int] = mutable.TreeMap[Int, Int](0 -> (n - 1))\n\n    case class Bound(left: Int, right: Int)\n\n    val minBounds = Array.ofDim[Bound](n)\n\n    def update(map: mutable.TreeMap[Int, Int], pos: Int): Unit = {\n      val (left, right) = map.rangeTo(pos).last\n      updateMap(map, left, pos - 1)\n      updateMap(map, pos + 1, right)\n    }\n\n    sortedArray.flatMap(item => {\n      val res = item.positions.map(pos => {\n        val (left, right) = minBoundMap.rangeTo(pos).last\n        pos -> Bound(left, right)\n      })\n\n      res.indices.foreach(i => update(minBoundMap, item.positions(i)))\n      res\n    })\n      .foreach { case (index, bound) => minBounds(index) = bound }\n\n    val maxBoundMap = mutable.TreeMap[Int, Int](0 -> (n - 1))\n\n    var srcIndex = sortedArray.length - 1\n\n    val maxBounds = Array.ofDim[Int](queries.length)\n    queries\n      .sortBy(-_.up)\n      .map(query => {\n\n        while (srcIndex >= 0 &amp;&amp; sortedArray(srcIndex).value > query.up) {\n          sortedArray(srcIndex).positions\n            .foreach(update(maxBoundMap, _))\n          srcIndex -= 1\n        }\n\n        val (left, right) = maxBoundMap.rangeTo(query.d).last\n        val minBound = minBounds(query.d)\n\n        query.index -> (math.min(minBound.right, right) - math.max(minBound.left, left) + 1)\n      })\n      .foreach { case (index, answer) => maxBounds(index) = answer }\n\n    println(maxBounds.mkString(\"\\n\"))\n  }\n}\n<\/pre>\n\n\n\n<p><strong>Note:<\/strong> This problem <strong>(<a href=\"https:\/\/www.hackerrank.com\/challenges\/stocks-prediction\/problem\" target=\"_blank\" rel=\"noreferrer noopener nofollow\">Stock Prediction<\/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 Stock Prediction HackerRank Solution. This problem (Stock Prediction) 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\/7342"}],"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=7342"}],"version-history":[{"count":3,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/7342\/revisions"}],"predecessor-version":[{"id":7346,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/posts\/7342\/revisions\/7346"}],"wp:attachment":[{"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/media?parent=7342"}],"wp:term":[{"taxonomy":"category","embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/categories?post=7342"},{"taxonomy":"post_tag","embeddable":true,"href":"https:\/\/www.codingbroz.com\/wp-json\/wp\/v2\/tags?post=7342"}],"curies":[{"name":"wp","href":"https:\/\/api.w.org\/{rel}","templated":true}]}}