BBK#7: Equal Sides 🤝

kotlin Jan 20, 2021

Don't be a Java-ish dev in Kotlin-ish world, improve your knowledge about Koltin Standard Library and write better Kotlin code. ✌🏻 If your Java dev migrating to Kotlin this will help you learn alot!

Featured On :

Question: For a given array, find Index N where the sum of integers to the left of N is equal to the sum of integers to the right of N, If there is no index that would make this return -1.

Example : 

for an array {1,2,3,4,3,2,1}
output would be 3 because at the 4th position of the array, 
the sum of left side of the index ({1,2,3}) and the sum of the right side of the index ({3,2,1}) both are equal to 6.

Try it yourself : 👨🏻‍💻👇🏻

Training on Equal Sides Of An Array | Codewars

Codewars is where developers achieve code mastery through challenge. Train on kata in the dojo and reach your highest potential.

Codewars

Some Code Philosophy Ranting..

I always categorize writing code into 3 levels.

Level 1 : Write for correctness

You just go all in without minding best practices or patterns, just aim for the right output on all of your use-cases. The only optimisation I suggest to do here is to keep your code readable and write descriptive names or at-least comments.

Level 2 : Refactor to make it maintainable

Once your code is working correctly, now is the time to make it maintainable, your aim is to preserve functionality, just update architecture, rename your variables, figure out ways to remove those comments and convert code into self expressive functions or variables. You DON'T change the functionality or algorithm used to solve the problem.

Level 3 : Optimize for memory and storage

90% of your code wouldn’t be needing this step if you have mastered level 1 and 2. You will come to this step only when its critical to business or to your app performance. Micro optimization just ruins your code, not make it good. Anyways In this step your aim is to keep algorithm and architecture intact don’t change it. You have to change data structure or replace internals of your functions with code which return out the same result in better performance.

Lets do it..

Naive Algorithm to solve this would be

Compute sum from first n items lets call it as leftSum
Compute sum remaining, i.e. n to last item of array, lets call it rightSum
if both sums are equal print the index, else print -1

Enjoying the Post?

a clap is much appreciated if you enjoyed. No sign up or cost associated :)

If you want to support my content do consider dropping a tip/coffee/donation💰

Solution 1 :


fun findEvenIndex(arr: IntArray): Int {

    var evenIndex = 0

    // Loop max till the size of array
    while (evenIndex != arr.size) {
        
        // sum accumulator loop
        var loopCounter = 0
        
        // indicates sum from left side
        var leftSum = 0

        // indicates sum of remaining items
        var rightSum = 0

        // loop till the end of list and compute left and write sums
        while (loopCounter != arr.size) {
            when{
                loopCounter < evenIndex -> leftSum += arr[loopCounter] 
                loopCounter == evenIndex -> {
                    leftSum+=arr[loopCounter]
                    rightSum+=arr[loopCounter]
                }
                else -> rightSum += arr[loopCounter]
            }
            ++loopCounter
        }

        // compare sum
        if (leftSum == rightSum) {
            // return found index
            return evenIndex
        } else {
            // proceed for second round in loop
            ++evenIndex
        }
    }

    // index not found
    return -1
}

// 👨🏻‍🔧 complexity : O(n^2)
// ⏱ performance : took 2.48 ms on my machine (this includes JVM startup time and could vary on your system)

This is the example how you don’t write the code, its fine when you are just getting started, but as your experience builds up, you need to make your code maintainable 👾.

Even with the descriptive naming without comments I need to create mental a map of every step and track what this code does. Also the common accumulator pattern issue of mutability is applied here.

Checkout why accumulator pattern in imperative style is bad.💡

Solution 2:

We were using accumulator to calculate sum, instead of that why don’t we split array into smaller chunks and find the sum ?

Let’s do that by using Sublist()


fun findEvenIndex(arr: IntArray): Int {
    val list = arr.toList()
    for (index in arr.indices) {
        val leftSum = list.subList(0, index + 1).sum()
        val rightSum = list.subList(index, arr.size).sum()
        if (leftSum == rightSum) {
            return index
        }
    }
    return -1
}

// 👨🏻‍🔧 complexity : O(n^2)
// ⏱ performance : took 22.5 ms on my machine (this includes JVM startup time and could vary on your system)

Compare to the solution 1, this code looks more maintainable, it doesn’t need comments and nesting is also controlled and api design regarding mutability is pretty much solid, but we can see also see solid hit on the performance, from ~2 ms to ~22 ms.

This code is on level 2 of my scaling, this performance hit is due to functions used. IntArray to List, then subListing into two different indexes.

This program needs level 3. Lets see what we can do, but even before that let me tell you something about subList,

SubList Ranting…

If you are coming from Java background, subList is the function that comes to your mind when you want to split the array on particular index, but there is an inherit issue hidden in this function, let's understand that with example.


  val list = mutableListOf(1, 2, 3, 4, 5)
  println(list)
  // output : [1, 2, 3, 4, 5]
  
  val subs = list.subList(0, 3)
  println(subs)
  // output : [1, 2, 3]
  
  println(list)
  // output : [1, 2, 3, 4, 5]

  list[0] = 5
  println(subs)
  // output : [5, 2, 3]
  
  println(list)
  // output : [5, 2, 3, 4, 5]

You see its using the same list reference to show you value in your subList, this could lead to accidental mutations, let's see next solution which is an example of Level 3 and also fixes this issue.

Checkout Other Big-Brain-Kotlin Series💡

Solution 3:

Another function that is available in Kotlin Stdlib that can split your array is Slice()

Unlike sublist it doesn’t use the same reference to the List, it generates a new copy. We also have sliceArray() which is specific to Arrays, instead of the List so we don’t have to covert our array to List and save one more computation.


fun findEvenIndex(arr: IntArray): Int {
    for (index in arr.indices) {
        val leftSum = arr.sliceArray(0 .. index).sum()
        val rightSum = arr.sliceArray(index .. arr.lastIndex).sum()
        if (leftSum == rightSum) {
            return index
        }
    }
    return -1
}

// 👨🏻‍🔧 complexity : O(n^2)
// ⏱ performance : took 2.48 ms on my machine (this includes JVM startup time and could vary on your system)

Nice, We have optimized our code from ~22 ms to ~2 ms and achieved Level 3.

Enjoying the Post?

a clap is much appreciated if you enjoyed. No sign up or cost associated :)

If you want to support my content do consider dropping a tip/coffee/donation💰

Bonus Solution

Ahm Ahm, yes my friend..


fun findEvenIndex(arr: IntArray) = arr.indices.indexOfFirst {
  arr.take(it).sum() == arr.drop(it + 1).sum()
}

// 👨🏻‍🔧 complexity : O(n^2)
// ⏱ performance : took 3.15 ms on my machine (this includes JVM startup time and could vary on your system)

Smoke KT every day.. 😂

Community Submission!

Thanks Marco89nish for submitting an fast O(n) solution :

fun solve(list: Iterable<Int>): Int {
    val sum = list.sum()
    list.foldIndexed(0) { index, acc, el ->
        if (acc + el == sum - acc) return index
        acc + el
    }
    return -1
}

Conclusion

Aim of these articles is not hate on Java, but to help people learn various ways in which they can write same logic better and more Kotlin standard library focused way.

Hope you find it informative and if you have any feedback or post request or want to subscribe to my mailing list forms are below.

Until next time. Happy Hacking! 👩‍💻