Execution speed comparison between mutable and immutable lists using Dynamic Programming method

LightningFastCoinChange.scala

// Fast solution using mutable list i.e. mutable.ArrayBuffer

import scala.annotation.tailrec
import collection.mutable.ArrayBuffer

object LightningFastCoinChange extends App {
  def coinChange(coins: Array[Int], amount: Int): Int = {
    val acc = ArrayBuffer.fill(amount + 1)(0)

    @tailrec
    def _coinChange(currAmt: Int): ArrayBuffer[Int] = {
      if (currAmt > amount) acc
      else {
        val xs = coins.map {coin =>
          if (currAmt >= coin) _backTrack(acc(currAmt - coin))
          else Int.MaxValue
        }
        acc(currAmt) = xs.min
        _coinChange(currAmt + 1)
      }
    }

    def _backTrack(x: Int): Int = if (x == Int.MaxValue) Int.MaxValue else x + 1

    if (amount == 0) 0 else {
      val result = _coinChange(1).last
      if (result == Int.MaxValue) -1 else result
    }
  }

  assert(coinChange(Array(1, 2, 5), 11) == 3)
  assert(coinChange(Array(2), 3) == -1)
  assert(coinChange(Array(186, 419, 83, 408), 6249) == 20)
  assert(coinChange(Array(1, 2, 3, 21), 63) == 3)
  assert(coinChange(Array(2), 4) == 2)
  assert(coinChange(Array(2), 1) == -1)
  assert(coinChange(Array(357, 239, 73, 52), 9832) == 35)
  assert(coinChange(Array(470, 35, 120, 81, 121), 9825) == 30)
}

QuickCoinChange.scala

// Slower solution using immutable List 

import scala.annotation.tailrec

object QuickCoinChange extends App {
  def coinChange(coins: Array[Int], amount: Int): Int = {

    @tailrec
    def _coinChange(currAmt: Int, acc: List[Int]): List[Int] = {
      if (currAmt > amount) acc
      else {
        val xs = coins.map {coin =>
          if (currAmt >= coin) _backTrack(acc.length - coin, acc(acc.length - coin))
          else Int.MaxValue
        }

        _coinChange(currAmt + 1, acc :+ xs.min)
      }
    }

    def _backTrack(balance: Int, x: Int): Int = if (x == Int.MaxValue) Int.MaxValue else x + 1

    if (amount == 0) 0 else {
      val result = _coinChange(1, List(0)).last
      if (result == Int.MaxValue) -1 else result
    }
  }

  assert(coinChange(Array(1, 2, 5), 11) == 3)
  assert(coinChange(Array(2), 3) == -1)
  assert(coinChange(Array(186, 419, 83, 408), 6249) == 20)
  assert(coinChange(Array(1, 2, 3, 21), 63) == 3)
  assert(coinChange(Array(2), 4) == 2)
  assert(coinChange(Array(2), 1) == -1)
  assert(coinChange(Array(357, 239, 73, 52), 9832) == 35)
  assert(coinChange(Array(470, 35, 120, 81, 121), 9825) == 30)
}