# Stock Prediction – HackerRank Solution

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

Contents

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 = {a0, a1, . . . , an-1}, which represents the average price per day of that stock. For a given dayÂ d (0 <= d < n)Â and marginÂ M, George needs to find the longest subarray containing the day’s entry as a minimum,Â ad, and all other entries not exceedingÂ ad + M.

That is, he has to find the longest subarray,Â A[l, r] = {al, al+1, . . . , ar}, such that

• 0 <= l <= d <= r < n

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Â A. The second line containsÂ nÂ space-separated integers,Â a0, a1, . . . , an-1, which represent the element of arrayÂ A. The next line contains the number of queriesÂ Q. Each of the subsequentÂ QÂ lines contain two integersÂ dÂ andÂ MÂ which represent the index of the element, which should be minimal and be included in subarray, and margin, respectively.

## Output Format

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

## Constraints

• 1 <= n <= 5 x 104
• 1 <= A[i] <= 109, 0 <= i < n
• 1 <= Q <= 105
• 0 <= d < n
• 0 <= M <= 109

Sample Input

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

Sample Output

``````2
3``````

Explanation

Query #1:Â The first element,Â a0 = 3, should be included in the subarray. SinceÂ a1 = 5Â is not less thanÂ 3 and does not cross the margin (3 + 2 = 5), it can be included. The third element,Â a2 = 2, 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[0, 1].

Query #2:Â HereÂ d = 2Â andÂ ad = 2. The next element,Â a3 = 6, is excluded because it is greater than the margin,Â 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Â A[0, 2]Â and have a length of 3.

## Solution – Stock Prediction – HackerRank Solution

Scala

```import java.io._
import java.util.StringTokenizer

import scala.collection.mutable

var st: StringTokenizer = _

def nextInt: Int = next.toInt

def nextLong: Long = next.toLong

def next: String = {
while (st == null || !st.hasMoreElements)
try
catch {
case e: IOException =>
e.printStackTrace()
}
st.nextToken
}

def nextDouble: Double = next.toDouble

def nextLine: String = {
var str = ""
try
catch {
case e: IOException =>
e.printStackTrace()
}
str
}
}

object Solution {
def main(args: Array[String]): Unit = {

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)
})