BBK#6: Equal sides 🤝

Don't be a Java-ish dev in a 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 a lot!

originally published on https://chetangupta.net/bbk7/

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 put yourself :
👨🏻‍💻👉 Try Yourself

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

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

Solution 1:

Same old imperative way. 😪

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 is an 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.💡

checkout 👉 Accumulator|Fold-Reduce

Solution 2:

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

Let’s do that by using Sublist()
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)
// ⏱ performance : took 22.5 ms on my machine

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.

Solve many more 👇🏻

Big-Brain-Kotlin

Solution 3:
Another function that is available in Kotlin Stdlib that can split your array is Slice()
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)
// ⏱ performance : took 2.48 ms on my machine

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

There is one bonus way to solve it in more concise ways.
for that you need to check out my personal site BBK-7:Equal Sides 🤝

Until next time. Happy Hacking! 👩‍💻

👥 Social

Stalk Me 👀 :

LinkedIn | Medium | Twitter | StackOverflow | CodeWars | WorkX |Github | Instagram | Youtube