Range Minimum Query – HackerRank Solution

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

Task

Range Minimum Query (RMQ) is a set of problems which deals with finding a property (here minimum) of a range. Segment Tree can be very helpful when solving with such problems. A segment tree is a tree like data structure which is used to store the information about intervals. Here’s the [(wiki link)] of it.

You are given a array of N integers, arr[0], arr[1], .., arr[(N-1)]. And you are given a list of ranges. For each range, (l, r) you have to find the minimum value between range arr[l], arr[l+1], arr[l+2], .., arr[r].

Input

First line will contain two integers, N M, length of array and number of queries. Then in next line, there are N space separated integers which represent the array, arr[0], arr[1], .., arr[N-1]. Then M line follows. Each M line will contain two integers, l r, representing a range.

Output

For each range, (l, r), you have to print the minimum integer in subarray arr[l], arr[l+1], .., arr[r] in separate line.

Constraints

  • 1 <= N, M <= 105
  • -105 <= arr[i] <= 105 , where 0 <= i < N
  • 0 <= l <= r < N

Sample Input

10 5
10 20 30 40 11 22 33 44 15 5
0 5
1 2
8 9
0 9
4 6

Sample Output

10
20
5
5
11

Explanation

  • For range (0, 5), subarray will be [10, 20, 30, 40, 11, 22]. So minimum value will be 10.
  • For range (1, 2), subarray will be [20, 30]. Minimum value = 20.
  • For range (8, 9), subarray is [15, 5]. Minimum value = 5.
  • For range (0, 9), Here we have to find the minimum (5) of the whole array.
  • For range (3, 5), subarray is [40, 11, 22]. Minimum value = 11.

Solution – Range Minimum Query – HackerRank Solution

Scala

import java.util.Scanner

case class Node(var value: Int)

class SegmentTree(len: Int) {
  val nodes: Array[Node] = Array.fill[Node](4 * len)(Node(Int.MaxValue))

  def add(index: Int, value: Int, v: Int = 1, left: Int = 0, right: Int = len - 1): Unit = {
    if (left != right) {
      val middle = (left + right) >> 1
      if (index <= middle) add(index, value, 2 * v, left, middle)
      else add(index, value, 2 * v + 1, middle + 1, right)

      nodes(v).value = combine(nodes(2 * v).value, nodes(2 * v + 1).value)
    }
    else {
      val node = nodes(v)
      node.value = value
    }
  }

  def query(leftBound: Int, rightBound: Int, v: Int = 1, left: Int = 0, right: Int = len - 1): Int = {
    if (leftBound == left && rightBound == right) {
      val node = nodes(v)
      node.value
    }
    else {
      val middle = (left + right) >> 1
      if (rightBound <= middle) query(leftBound, rightBound, 2 * v, left, middle)
      else if (leftBound > middle) query(leftBound, rightBound, 2 * v + 1, middle + 1, right)
      else combine(
        query(leftBound, middle, 2 * v, left, middle),
        query(middle + 1, rightBound, 2 * v + 1, middle + 1, right)
      )
    }
  }

  def combine(leftValue: Int, rightValue: Int): Int = math.min(leftValue, rightValue)
}

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

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

    val tree = new SegmentTree(arr.length)
    arr.indices.foreach(i => tree.add(i, arr(i)))

    (0 until m).foreach(_ => {
      val left = sc.nextInt
      val right = sc.nextInt

      println(tree.query(left, right))
    })

    sc.close()
  }
}

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

Leave a Comment

Your email address will not be published. Required fields are marked *