Confused over reverse, reversed, and asReveresed ? in Kotlin

Confused over reverse, reversed, and asReveresed ? in Kotlin

Let’s solve a question and learn more about it.

Originally post on https://chetangupta.net/bbk8/

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 put yourself 👨🏻‍💻👇🏻: geeksforgeeks.org/write-a-program-to-revers..

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! Let’s analyze this approach and see the Pros and Cons :

Pros :

  • It’s an extension function — which means would only be visible on Receivers it’s assigned to, here Receiver is List and reverseExtraSpace function would be visible to this only. (we can make it more generalized using generics)
  • The input list is not getting modified i.e. after reversing if we made changes in the original list it would be accidentally reflected into the reversed list.
  • Mutations are scope in the body of the extension only, you get a read-only list from the return type. All in all this code is very safe and sound.

Cons :

  • It has to iterate over the 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 …

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.

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:

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 using reversed over asReversed.

Bonus Part — Reverse

Talking about Mutable-List, we have an additional reverse function — kotlinlang.org/api/latest/jvm/stdlib/kotlin.. 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]

i.e. use it wisely.

Conclusion 💆🏻‍♀️

That’s all folks! Hope this helps someone. 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.

chetangupta.net/updates

Do consider Clap to show your appreciation, until next time. Happy Hacking! 👩‍💻