Big Brain Kotlin - Reverse an Array/List/String.

bbk Apr 21, 2022

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

Note - The aim of this series is not to teach you problem-solving you might be way better at that than me, we are here to learn and use standard library functions or learn to be a better developer with Kotlin APIs. 

*Spoilers* Using the scope function doesn't make you code more Kotlin-ish.

Hi, I’m back with another question, and it's very common and easy. You might have done this zillions of times.

Question: Write a program to reverse an array or string :

Example :
Input1 :  arr[] = {4, 5, 1, 2}
Output : arr[] = {2, 1, 5, 4}

Try it yourself : 👨🏻‍💻👇🏻

Well before we go into Kotlin’s standard library solution let's look at ways to solve it manually :

Solution 1 : Taking Extra Space 🪣

by taking extra space I mean we will use another list to reverse the list,

fun main() {
    val input1 = listOf(4, 5, 1, 2)
    println(input1.reverseExtraSpace()) // [2, 1, 5, 4]
}

fun List<Int>.reverseExtraSpace(): List<Int> {
    val result = mutableListOf<Int>()
    for (index in indices) {
        val lastIndex = lastIndex - index
        result.add(get(lastIndex))
    }
    return result
}

Vola! with lots of code we are done reversing our array!
Lets analyse this approach and see Pros and Cons :

Pros :

It’s an extension function - means would only be visible on Receivers its assigned to, here Receiver is List<Int> and reverseExtraSpace function would be visible to this only. (we can make it more generalized using generics)
Input list is not getting modified i.e. after reversing if we made changes in original list it would be accidentally reflected into reversed list.
Mutations are scope in the body of extension only, you get read-only list from return type.

All in all this code is very safe and sound.

Cons :

It has to iterate over entire list
We take more space to store reversed list.

…huh.. what do you mean this approach is not good? The interviewer will ask to optimize for space.

Well when we are in an interview setting we have to show them our A-Game in terms of using your brain, but you need to explain to them as well writing code for correct and predictable behavior is much more important, than minor optimization. It should be the last part of your code evaluation metric unless it impacts the usability of the application.

but in case he didn’t agree and insist on the better solution then …

Learn to Implement LRU cache from scratch💡

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 2 : Not Taking Extra Space 🚀

So we will not create any array.


fun main() {
    val input1 = listOf(4, 5, 1, 2)
    println(input1.reverseNoExtraSpace()) // [2, 1, 5, 4]
}

fun List<Int>.reverseNoExtraSpace(): List<Int> = with(this.toMutableList()) {
    val mid = lastIndex / 2
    (0..mid).forEach {
        val firstIndex = it
        val lastIndex = lastIndex - it
        val first = get(firstIndex)
        val last = get(lastIndex)
        //swap
        set(firstIndex, last)
        set(lastIndex, first)
    }
    this
}

and done! without using extra space.

It’s very easy to mess up implementation and loss the Pros of Solution 1, remember its important to understand what kind of data you are sending as input, exposing as output and scope in which mutation should be allowed.

Note in Kotlin that when we convert list to a Mutable list isn't a typecast, a new mutable list with the same items gets created. To remove that cost you need to take MutableList instead of List from the beginning. 

Or you can use IntArray if you like.

Checkout Other Big-Brain-Kotlin Series💡

Solution 3 : Using Standard Library Functions 🎒

Now the nice part, by going through these solutions you already have know-how under the hood reverse operation works. In Kotlin standard library uses solution 2 as its base.
On our List collection, we have two ways to reverse the order of the list:

Reversed :

asReversed :

both of them returns list in reversed order, but when you use reversed any changes done in original list is not reflected in reversed list. Thus make it safer to use it with mutable collections.

Example :
val list = mutableListOf(1,2,3,4) // mutable list
val reversed   = list.reversed()
val asReversed = list.asReversed()

println(list) // [1,2,3,4]
println(reversed) // [4,3,2,1]
println(asReversed) // [4,3,2,1]

list.set(1,9)

println(list) // [1,9,3,4]
println(reversed) // [4,3,2,1]
println(asReversed) // [4,3,9,1]

Note - If you are using List which is a read-only collection this issue isn’t there at all. because you can’t modify a List unless you convert it into a Mutable List, and even if you try to convert it would be an entirely new list, not the same list which you have reversed. So for List using reversed and asReversed is similar.

but for a general rule, I will strongly recommend to use reversed over asReversed.

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 Part - Reverse

Talking about Mutable-List, we have additional reverse function -

it Reverses elements in the list in-place, which means :

val input = mutableListOf(1,2,3,4,5)
println(input) // [1, 2, 3, 4, 5]
input.reverse() // retuns Unit not a list i.e. updates the exisiting list
println(input) // [5, 4, 3, 2, 1]

This means, use it wisely or avoid.

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! 👩‍💻