In this post, we will solve **Stock Prediction HackerRank Solution**. This problem **(Stock Prediction)** is a part of **HackerRank Functional Programming** series.

**Task**

George is very concerned about the stock options his company has granted him, because the company’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.

Stock price history is presented as an array of positive integers, ** A = {a_{0}, a_{1}, . . . , a_{n-1}}**, which represents the average price per day of that stock. For a given day

**and margin**

*d*(0 <=*d*<*n*)*, George needs to find the longest subarray containing the day’s entry as a minimum,*

**M****, and all other entries not exceeding**

*a*_{d}**.**

*a*_{d}+ MThat is, he has to find the longest subarray, ** A[l, r] = {a_{l}, a_{l+1}, . . . , a_{r}}**, such that

**0 <=***l*<=*d*<=*r*<*n**a*_{d}=*minimum*{*A*[*l*,*r*]}*i*∈[*l*,*r*],*a*_{d}<=*a*_{i}<=*a*_{d}+ M

George asks you to help him solve this problem.

**Input Format**

The first list contains an integer * n* which represents the length of the array

*. The second line contains*

**A***space-separated integers,*

**n****, which represent the element of array**

*a*_{0},*a*_{1}, . . . ,*a*_{n-1}*. The next line contains the number of queries*

**A***. Each of the subsequent*

**Q***lines contain two integers*

**Q***and*

**d***which represent the index of the element, which should be minimal and be included in subarray, and margin, respectively.*

**M****Output Format**

For each query output the length of the longest subarray with the required properties.

**Constraints**

**1 <=***n*<= 5 x 10^{4}**1 <=***A*[*i*] <= 10^{9}, 0 <=*i*<*n***1 <=***Q*<= 10^{5}**0 <=***d*<*n***0 <=***M*<= 10^{9}

**Sample Input**

```
5
3 5 2 6 1
2
0 2
2 3
```

**Sample Output**

```
2
3
```

**Explanation**

*Query #1:* The first element, ** a_{0} = 3**, should be included in the subarray. Since

**is not less than**

*a*_{1}= 5**3**and does not cross the margin (

**3 + 2 = 5**), it can be included. The third element,

**, 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**

*a*_{2}= 2**.**

*A*[0, 1]*Query #2:* Here ** d = 2** and

**. The next element,**

*a*_{d}= 2**, is excluded because it is greater than the margin,**

*a*_{3}= 6**2 + 3 = 5**. All of the previous elements will be included, as they are within the allowed range

**[2, 5]**. To that end, the longest subarray will be

**and have a length of 3.**

*A*[0, 2]**Solution – Stock Prediction – HackerRank Solution**

**Scala**

import java.io._ import java.util.StringTokenizer import scala.collection.mutable class FastReader() { val br: BufferedReader = new BufferedReader(new InputStreamReader(System.in)) var st: StringTokenizer = _ def nextInt: Int = next.toInt def nextLong: Long = next.toLong def next: String = { while (st == null || !st.hasMoreElements) try st = new StringTokenizer(br.readLine) catch { case e: IOException => e.printStackTrace() } st.nextToken } def nextDouble: Double = next.toDouble def nextLine: String = { var str = "" try str = br.readLine catch { case e: IOException => e.printStackTrace() } str } } object Solution { def main(args: Array[String]): Unit = { val sc = new FastReader val n = sc.nextInt val arr = (0 until n).map(_ => sc.nextInt) case class Query(index: Int, d: Int, up: Int) val m = sc.nextInt val queries = (0 until m).map(i => { val d = sc.nextInt Query(i, d, arr(d) + sc.nextInt) }) def updateMap(map: mutable.Map[Int, Int], left: Int, right: Int): Unit = if (left <= right) map += (left -> right) else map -= left case class Item(value: Int, positions: IndexedSeq[Int]) extends Ordered[Item] { override def compare(that: Item): Int = this.value.compareTo(that.value) } val tempMap = mutable.Map[Int, List[Int]]() arr.indices.foreach(i => { val v = arr(i) tempMap += v -> (i :: tempMap.getOrElse(v, Nil)) }) val sortedArray = tempMap.map { case (v, list) => Item(v, list.toIndexedSeq) }.toIndexedSeq.sorted val minBoundMap: mutable.TreeMap[Int, Int] = mutable.TreeMap[Int, Int](0 -> (n - 1)) case class Bound(left: Int, right: Int) val minBounds = Array.ofDim[Bound](n) def update(map: mutable.TreeMap[Int, Int], pos: Int): Unit = { val (left, right) = map.rangeTo(pos).last updateMap(map, left, pos - 1) updateMap(map, pos + 1, right) } sortedArray.flatMap(item => { val res = item.positions.map(pos => { val (left, right) = minBoundMap.rangeTo(pos).last pos -> Bound(left, right) }) res.indices.foreach(i => update(minBoundMap, item.positions(i))) res }) .foreach { case (index, bound) => minBounds(index) = bound } val maxBoundMap = mutable.TreeMap[Int, Int](0 -> (n - 1)) var srcIndex = sortedArray.length - 1 val maxBounds = Array.ofDim[Int](queries.length) queries .sortBy(-_.up) .map(query => { while (srcIndex >= 0 && sortedArray(srcIndex).value > query.up) { sortedArray(srcIndex).positions .foreach(update(maxBoundMap, _)) srcIndex -= 1 } val (left, right) = maxBoundMap.rangeTo(query.d).last val minBound = minBounds(query.d) query.index -> (math.min(minBound.right, right) - math.max(minBound.left, left) + 1) }) .foreach { case (index, answer) => maxBounds(index) = answer } println(maxBounds.mkString("\n")) } }

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