codility solution

MaxCounters.scala

import scala.collection.immutable.HashMap

object Demo extends App {

  sealed trait Input
  object Input{
    final case class IncrementCounter(humanIndex: Int) extends Input
    case object MaxCounter extends Input

    def fromInt(n: Int, arraySize: Int): Input = if (n <= arraySize){
      IncrementCounter(n)
    } else {
      MaxCounter
    }
  }

  final case class State(mapping: Map[State.ArrayIndex, Int], max: Int, min: Int) {
    def get(arrayIndex: State.ArrayIndex): Int = mapping.get(arrayIndex).filter(_ > min).getOrElse(min)

    def incrementByOne(arrayIndex: State.ArrayIndex): State = {
      val newValue = get(arrayIndex) + 1
      val newMax = if(newValue > max){newValue} else max
      copy(mapping = mapping.updated(arrayIndex, newValue), max = newMax)
    }

    def setAllToMax: State = copy(min = max)
  }
  object State{
    final case class ArrayIndex(value: Int) extends AnyVal
    object ArrayIndex{
      def fromHumanIndex(i: Int): ArrayIndex = ArrayIndex(i - 1)
    }

    def empty: State = State(HashMap.empty, max = 0, min = 0)
  }

  def solution(n: Int, a: Array[Int]): Array[Int] = {
    val state = a.toList.foldLeft(State.empty){ case (s, i) =>
      Input.fromInt(i, n) match {
        case Input.IncrementCounter(humanIndex) => s.incrementByOne(State.ArrayIndex.fromHumanIndex(humanIndex))
        case Input.MaxCounter => s.setAllToMax
      }
    }

    val response = new Array[Int](n)
    Range(0, n).foreach( i =>
      response(i) = state.get(State.ArrayIndex(i))
    )

    response
  }

  println(
    solution(
      5,
      Array(3, 4, 4, 6, 1, 4, 4)
    ).mkString("Array(", ", ", ")")
  )
}

The idea behind this solution is:

• We don't store the variables we don't need. think of these parameters: n=5, a= Array(1,1,1,1,1,1,1,1,...)
• min, max cache the global information about our mappings and save us the dynamic lookup.
• setAllToMax / max_counter doesn't go around and update all the existing values.
• we avoid Array.filling with min at the end. Think about the parameters: n=5, a= Array(1,6,6,6,6,6,6,6,6,...)

The second revision which uses a fold (as opposed to the foreach based first revision that uses Unit return type for State methods, would not pass 100% on performance score unless you add the a.toList bit. not exactly sure why.