sorted squared array

this time we will try to (satisfactory) solve a coding challenge.

description

write a function that takes in a non-empty array of integers that are sorted in ascending order and returns a new array of the same length with the squares of the original integers also sorted in ascending order.

first attempt

first attempt (which fails when array includes negative numbers) given array = [-2, -1] as input, output is [4, 1] which is wrong because correct output should be sorted in ascending order:

first-attempt.kts

#!/usr/bin/env kscript

fun sortedSquaredArray(array: List<Int>): List<Int> {
    return array.map { n -> n * n }
}

what i like from first-attempt (failed) solution is that we have no state (we are not mutating anything), we are only traversing our input array once and generating a new array as our output.

second attempt

an optimal solution would be to use a data structure that preserves the order of its elements i.e binary tree; but, given that we have no b-tree at our disposal we can leverage Kotlin native BinarySearch methods in List. we need to be careful with the return value of such a function in order to prevent index bound exceptions:

second-attempt.kts

#!/usr/bin/env kscript

fun sortedSquaredArray(array: List<Int>): List<Int> {
    val acc = mutableListOf<Int>()

    for (n in array) {
        val sqr = n * n

        if (acc.isEmpty()) acc.add(sqr)
        else {
            val i = (acc.binarySearch(sqr, 0, acc.size) + 1).absoluteValue
            acc.add(i, sqr)
        }
    }

    return acc
}

what i dislike from second-attempt solution is that: we have state mutations. on the other hand, i like that we are still traversing our input array once meaning O(n) complexity which I think is nice!

bonus

as a bonus here is a 3rd optional solution that is not as efficient as the previous one but this third solution is based on immutable data structures which is always good:

Kotlin

bonus-attempt.kts

#!/urs/bin/env kscript

fun sortedSquaredArray(array: List<Int>): List<Int> {

    fun add(n: Int, list: List<Int>): List<Int> {
        val (l, g) = list.partition { x -> x <= n }
        return l.plus(n).plus(g)
    }

    return array.fold(listOf()) { acc, n ->
        add(n * n, acc)
    }
}

Scala

scala-bonus.worksheet.sc

/**
 * scala 3.1.0
 */

// binary-search based (not stack-safe)
final def add(list: List[Int], n: Int): List[Int] =
   list match
     case Nil => List(n)
     case x :: Nil if n >= x => list :+ n
     case x :: Nil if n < x  => n +: list
     case _ =>
       val size = list.size
       val middleIndex: Int = size  / 2
       val middleValue: Int = list(middleIndex)
       val (l, g) = list.splitAt(middleIndex)
       if n > middleValue then
         l ++ add(list.slice(middleIndex, size), n)
       else
         add(list.slice(0, middleIndex), n) ++ g

def sortedSquaredArray(list: List[Int]): List[Int] =
  list.foldLeft(List.empty) { (acc, n) =>
    add(acc, n * n)
  }

val result =sortedSquaredArray(List(-3, -2, 1))
assert(result == List(1, 4, 9))

PD. in case you are wondering bout the kscript in the codeblocks take a look at: holgerbrandl/kscript