How to efficiently remove var in Scala

Question

I am trying to solve problem https://www.geeksforgeeks.org/connect-n-ropes-minimum-cost/

Solution

def minCost(arr: Array[Int]):Int = {

  val minHeap = scala.collection.mutable.PriorityQueue.empty[Int].reverse
    
  arr.foreach{ ele =>
    minHeap += ele
  }
    
  var sum =0
    
  while(minHeap.size >1){
    
    val first = minHeap.dequeue()
    val second = minHeap.dequeue()
    
    val length = second + first//3+3 =6+9
    sum = sum + (first +second)//3+6+9
    
    minHeap.enqueue(length)
  }
    
  sum
}

I want to get rid of while loop and var. Can anyone suggest a better solution?

tried below

val res =minHeap.foldLeft(0){
  (x,y)=>
    val sum =x+y
    minHeap.enqueue(sum)
    sum
}

println(res)
res

Answer 1

If you only want to remove the var and while but still use a mutable PriorityQueue (which being honest is a good compromise and probably the best to do in real code) you can just use a tail-recursive method.

type Ropes = List[Int]

def connectRopes(ropes: Ropes): Int = {
  val queue = PriorityQueue.from(ropes).reverse
  
  @annotation.tailrec
  def loop(remaining: Int, acc: Int): Int = {
    if (remaining == 0) acc
    else if (remaining == 1) acc
    else {
      val rope1 = queue.dequeue()
      val rope2 = queue.dequeue()
      val newRope = rope1 + rope2
      queue.addOne(newRope)
      loop(remaining - 1, acc + newRope)
    }
  }
  
  loop(remaining = queue.size, acc = 0)
}

But, if you want to write a fully immutable solution just to get used to work with immutable data structures you can do something like this:

def connectRopesFullImmutable(ropes: Ropes): Int = {
  @annotation.tailrec
  def loop(remaining: Ropes, acc: Int): Int =
    remaining match {
      case Nil =>
        acc
      
      case _ :: Nil =>
        acc
      
      case rope1 :: rope2 :: Nil =>
        rope1 + rope2 + acc
      
      case rope1 :: rope2 :: tail =>
        @annotation.tailrec
        def findTwoMin(remaining: Ropes, min1: Int, min2: Int, acc: Ropes): (Int, Int, Ropes) =
          remaining match {
            case rope :: tail =>
              if (rope < min1) findTwoMin(remaining = tail, min1 = rope, min2 = min1, min2:: acc)
              else if (rope < min2) findTwoMin(remaining = tail, min1, min2 = rope, min2 :: acc)
              else findTwoMin(remaining = tail, min1, min2, rope :: acc)
            
            case Nil =>
              (min1, min2, acc)
          }
      
        val (min1, min2, ropes) =
          if (rope1 < rope2) findTwoMin(remaining = tail, min1 = rope1, min2 = rope2, acc = List.empty)
          else findTwoMin(remaining = tail, min1 = rope2, min2 = rope1, acc = List.empty)
        val newRope = min1 + min2
        loop(remaining = newRope :: ropes, acc + newRope)
    }
  
  loop(remaining = ropes, acc = 0)
}

---

Answering the comment the space complexity of the problem is (AFAIK) O(1), since the algorithm is a tail-recursive function we are not consuming stack and we only manipulate the same list so we are also not consuming heap.
The time complexity is O(N^2) because we have an inner loop inside the outer loop, this means this algorithm is very inefficient.

We may try to optimize it a little by keeping the list of remaining ropes always sorted; as shown below. Which should give use O(N log(N)), but still requires a lot of boilerplate and inefficiency just for not using a mutable priority queue.

def connectRopesFullImmutableOptimized(ropes: Ropes): Int = {
  @annotation.tailrec
  def loop(remaining: Ropes, acc: Int): Int =
    remaining match {
      case rope1 :: rope2 :: tail =>
        val newRope = rope1 + rope2
      
        @annotation.tailrec
        def insertSorted(remaining: Ropes, acc: Ropes): Ropes =
          remaining match {
            case rope :: ropes =>
              if (newRope > rope) insertSorted(remaining = ropes, rope :: acc)
              else acc reverse_::: (newRope :: rope :: ropes)
            
            case Nil =>
              (newRope :: acc).reverse
          }
      
        loop(remaining = insertSorted(remaining = tail, acc = List.empty), acc + newRope)
      
      case _ =>
        acc
    }
  
  loop(remaining = ropes.sorted, acc = 0)
}

---

You can see the code running in Scastie.