Scala Codility GenomicRangeQuery performance
The basic task here is to search for the minimum value in the current subset, but there is a known floor value so it would be nice if we could terminate the search early if the floor value is encountered. Unfortunately the Standard Library doesn't have such an animal so we'll have to roll our own.

def solution(s: String, p: Array[Int], q: Array[Int]): Array[Int] = {

  val arr = s.toArray.map {   // String to Array of weighted values
    case 'A' =&gt; 1
    case 'C' =&gt; 2
    case 'G' =&gt; 3
    case 'T' =&gt; 4
  }

  def subMin(start: Int, end: Int, min: Int = 4): Int =
    if (start &gt; end) min                                          // search done
    else if (arr(start) == 1 || arr(end) == 1) 1                  // early end
    else subMin(start+1, end-1, arr(start) min arr(end) min min)  // tail recurse

  p.indices.map(x =&gt; subMin(p(x), q(x))).toArray
}


With this I got 100% correctness and 66% performance.

So a different, and perhaps larger, performance issue is that once a subset has been evaluated it would be really nice if we never have to revisit it again, just recall the previous evaluation when needed.

That's the basic idea behind a segment tree. Essentially, your data becomes the leaves of a binary tree and each node contains the result of the associative operation on all the leaf values underneath it.

I won't paste the 40 lines of segment tree code here (worthy of independent study), but with that in place...

def solution(s: String, p: Array[Int], q: Array[Int]): Array[Int] = {

  val arr = s.toArray.map {   // String to Array of weighted values
    case 'A' =&gt; 1
    case 'C' =&gt; 2
    case 'G' =&gt; 3
    case 'T' =&gt; 4
  }

  val st = SegmentTree(arr, Math.min)  // build the segment tree

  p.indices.map(x =&gt; st(p(x), q(x))).toArray
}


... this got 100% correctness and 100% performance.