CODEWITHSUNDEEP
kotlin
Andrew
Andrew

Reputation: 4702

Kotlin: How to check fast if list2 contains one item of list1

I am trying to check if a given list2 contains at least one item of given list1. If so, I would like to return true. My current approach is:

val object1 = Object1(body = listOf(1,2,3))
val object2 = Object1(body = listOf(2,5,7)

val doesList2ContainList1: Boolean = object2.body.intersect(object1.body).any() ==> should return true

I doubt that this is the fastest possible way to check if object2.body contains one item of object1.body because it checks the whole list, creates a new one and then executes any() right? But I want to instantly return true if one item of list2 is in list1. I have to make sure that this is really fast because object1.body and or object2.body can become really large.

I appreciate every help. Thank you

Upvotes: 0

Views: 1737

Answers (1)

Rubydesic
Rubydesic

Reputation: 3476

intersect internally uses a set, so O(n). You can make it faster though (even though not with better time complexity), if performance is really a concern. For example:

fun <T> Collection<T>.containsAny(other: Collection<T>): Boolean {
    // Use HashSet instead of #toSet which uses a LinkedHashSet 
    val set = if (this is Set) this else HashSet(this)
    for (item in other)
        if (set.contains(item)) // early return
            return true
    return false
}

Upvotes: 4

Related Questions