Retrieving largest indices of the bounded element in a multidimensional array in Scala

Question

I have an multidimensional Array:

val M = Array.ofDim[Int](V, N)

Goal is to find largest V dimension index for which there exists a bounded element 0 < w0 <= W and return both indices and element value.

Currently I have this code snippet which works, but wondering if there is a nicer, more efficient way to do this.

M.zipWithIndex.reverse.collectFirst({
  case (arr, ind) if arr.exists(a => a <= W && a > 0) => {
    arr.zipWithIndex.find(a => a._1 <= W && a._1 > 0) match {
      case Some((weight, ind2)) => (ind, ind2, weight)
    }
  }
})

Answer 1

You're really better off with an imperative or recursive solution here. I'll write a recursive one:

def finder(arr: Array[Array[Int]], w: Int, i: Int = 0, j: Int = 0): Option[(Int,Int,Int)] = {
  val ri = arr.length-i-1
  if (i >= arr.length) None
  else if (arr(ri)(j) > 0 && arr(ri)(j) < w) Some(ri,j,arr(ri)(j))
  else if (j+1 < arr(i).length) finder(arr,w,i,j+1)
  else finder(arr,w,i+1)
}

Then finder(M,W) should do what you want. Note that this is also efficient--no boxing aside from the return value.

---

Edit--if you care about performance, here are the runtimes of the existing solutions on a 100x100 array which has no solutions or one solution at 77% of the way to the end (i.e. runtime should be about 1/4):

Original without answer:     65 μs / iteration
Original with answer at 1/4: 18 μs / iteration

Result table compared to original method, relative time taken (lower is faster, compiled with -optimise but that hardly makes a difference):

                  No Answer    1/4 Answer
Original            1.00          1.00
Rex                 0.55          0.72
4e6                 1.95          7.00
missingfaktor       2.41          1.91
Luigi               4.93          3.92

So your original method was actually faster than all of the suggestions, save for the recursive one.