How to compare two lists item by item in Kotlin

Question

how can i compare "List A" with "List B", and if "list A", has "n" elements that match with "list B" create a "C list" from the "list A" with boolean attached as a new field to every item so if the item was in "list B" it is true else false.

heres a detailed example of what im trying to do:

data class ListAelement(
    val fieldA: Double = 2.0,
    //this is the field that i have to check with listB
    val id: String = "12345",
    val somefield: String,
    val someotherfield: String
)

data class ListBelement(
    //list b only has id
    val id: String = "12345"
)

data class ListCelement(
    val fieldA: Double = 2.0,
    val id: String = "12345",
    val somefield: String,
    val someotherfield: String,
    //this should be true if it is in ListB
    val isElementInA: Boolean
)



fun isEqual(listA: List<ListAelement>, listB: List<ListBelement>): List<ListCelement> {
    
   
    return emptyList()
}



fun main() {
    val listA = listOf<ListAelement>(
        ListAelement(1.2, "12345"),
        ListAelement(1.2, "12343"),
        ListAelement(1.2, "1234566"),
        ListAelement(1.2, "11233")
    )
    val listB = listOf<ListBelement>(ListBelement("12345"), ListBelement("123123"))
    //new list
    val listC = isEqual(listA, listB)

}

Tried following

val listASize = listA.size 
val listBSize = listB.size 
var counter = 0 
while (counter < listASize) { 
    var id = listA[counter].id 
    listB.forEach { 
         if (it.id == id) { 
           println("matched item $it") 
         } 
    } 
    counter++ 
} 

the accepted response works as it should, heres what i was trying to achieve:

"list A" is an Api response, "list B" is a local database, and list C is to display it and show a check if the item is in the local database

Answer 1

Essentially what you have is a search problem.

I have slightly modified your implementation to make it more accurate for reference:

fun isEqual(listA: List<ListAelement>, listB: List<ListBelement>): List<ListCelement> {

    val listC: MutableList<ListCelement> = mutableListOf()

    // you don't need a while loop or a counter variable as you need to look at every item in list A
    listA.forEach { listAItem ->
        var found = false

        // search for each item in list A in list B
        // this is a linear search
        listB.forEach { listBItem -> 
             if (listBItem.id == listAItem.id) { 
               // println("matched item $it") 
               found = true // cache the result that it has been found rather than printing out
             } 
        }

        // create your list C with the ListCelement instance that holds the result of whether it was found in List B or not
        listC.add(
            ListCelement(id=listAItem.id, isElementInA=found)
        ) 
    }

    return listC
}

You current implementation is of time complexity=O(N * M) (where N and M are the sizes of lists A and B) because for each item in list A, you have to iterate through list B while performing a linear search for it.

This can be optimized through the use of a binary search. Binary search does however require that the search space is sorted. In your case list B being the search space, it needs to be sorted on the id field since that's what you identify elements of list A that are in list B on.

It has a time complexity=O(log N) (where N is the size of the search space) because you take advantage of the order in your search space to discard half the elements at each attempt until you either find your search item or reduce your search space to one item which is not your search item in which case you exit the search.

Below is an implementation using binary search:

/**
 * We declare a package-level function main which returns Unit and takes
 * an Array of strings as a parameter. Note that semicolons are optional.
 */
data class ListAelement(
    val fieldA: Double = 2.0,
    // this is the field that i have to check with listB
    val id: String,
    val someField: String,
    val someOtherField: String
)

data class ListBelement(
    // list b only has id
    val id: String
)

data class ListCelement(
    val fieldA: Double = 2.0,
    val id: String,
    val someField: String,
    val someOtherField: String,
    // this should be true if it is in ListB
    val isElementInA: Boolean
)

fun isEqual(listA: List<ListAelement>, listB: List<ListBelement>): List<ListCelement> {
    val sortedListB = listB.sortedWith(compareBy({ it.id }))

    val listC: MutableList<ListCelement> = mutableListOf()
    
    listA.forEach { listAItem ->    
        listC.add(
            ListCelement(
                id=listAItem.id, 
                someField=listAItem.someField,
                someOtherField=listAItem.someOtherField,
                isElementInA=binarySearchListB(sortedListB, listAItem) // linear search replaced with this binary search
            )
        )
    }
    return listC
}

// the kotlin collections package ships with a binarySearch() function https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/binary-search.html
// I have opted to implement a custom one so that I can have a Boolean return type
fun binarySearchListB(searchSpace:List<ListBelement>, searchItem: ListAelement, leftIndex:Int = 0, rightIndex: Int = searchSpace.size - 1): Boolean {
    val midIndex: Int = (leftIndex + rightIndex) / 2
    val midItem: ListBelement = searchSpace[midIndex]

    // exit condition if item does not exist
    if (leftIndex == rightIndex && searchItem.id != searchSpace[leftIndex].id) {
        return false
    }

    if (midItem.id == searchItem.id) {
        // found
        return true
    } else if(searchItem.id < midItem.id) {
        // go to the left
        return binarySearchListB(searchSpace, searchItem, leftIndex, midIndex - 1)
    } else if(searchItem.id > midItem.id) {
        // go to the right
        return binarySearchListB(searchSpace, searchItem, midIndex + 1, rightIndex)
    }
    return false
}

fun main(args: Array<String>) {
    val listA = listOf<ListAelement>(
        ListAelement(1.2, "12345", "someField", "someOtherField"),
        ListAelement(1.2, "12343", "someField", "someOtherField"),
        ListAelement(1.2, "1234566", "someField", "someOtherField"),
        ListAelement(1.2, "11233", "someField", "someOtherField")
    )
    val listB = listOf<ListBelement>(ListBelement("1234566"), ListBelement("12345"), ListBelement("123123"))
    // new list
    val listC = isEqual(listA, listB)
    println(listC)
}

Here is the output:

[ListCelement(fieldA=2.0, id=12345, someField=someField, someOtherField=someOtherField, isElementInA=true), ListCelement(fieldA=2.0, id=12343, someField=someField, someOtherField=someOtherField, isElementInA=false), ListCelement(fieldA=2.0, id=1234566, someField=someField, someOtherField=someOtherField, isElementInA=true), ListCelement(fieldA=2.0, id=11233, someField=someField, someOtherField=someOtherField, isElementInA=false)]

UPDATE:

Here's an update that converts list B into a HashSet of strings containing ListBelement ids to yield constant time lookups (i.e O(1)) as suggested in the comments:

/**
 * We declare a package-level function main which returns Unit and takes
 * an Array of strings as a parameter. Note that semicolons are optional.
 */
data class ListAelement(
    val fieldA: Double = 2.0,
    // this is the field that i have to check with listB
    val id: String,
    val someField: String,
    val someOtherField: String
)

data class ListBelement(
    // list b only has id
    val id: String
)

data class ListCelement(
    val fieldA: Double = 2.0,
    val id: String,
    val someField: String,
    val someOtherField: String,
    // this should be true if it is in ListB
    val isElementInA: Boolean
)

fun isEqual(listA: List<ListAelement>, listB: List<ListBelement>): List<ListCelement> {
    // construct a HashSet of string ids from listB
    // there could be a more idiomatic way to do it
    // more about HashSet here -> https://kotlinlang.org/api/latest/jvm/stdlib/kotlin.collections/-hash-set/
    val listBHashSet: HashSet<String> = hashSetOf()
    listB.forEach { listBItem -> 
        listBHashSet.add(listBItem.id)
    }
    
    val listC: MutableList<ListCelement> = mutableListOf()
    
    listA.forEach { listAItem ->    
        listC.add(
            ListCelement(
                id=listAItem.id, 
                someField=listAItem.someField,
                someOtherField=listAItem.someOtherField,
                isElementInA=listBHashSet.contains(listAItem.id) // linear search replaced with this hashset lookup search
            )
        )
    }
    return listC
}

fun main(args: Array<String>) {
    val listA = listOf<ListAelement>(
        ListAelement(1.2, "12345", "someField", "someOtherField"),
        ListAelement(1.2, "12343", "someField", "someOtherField"),
        ListAelement(1.2, "1234566", "someField", "someOtherField"),
        ListAelement(1.2, "11233", "someField", "someOtherField")
    )
    val listB = listOf<ListBelement>(ListBelement("1234566"), ListBelement("12345"), ListBelement("123123"))
    // new list
    val listC = isEqual(listA, listB)
    println(listC)
}

The output:

[ListCelement(fieldA=2.0, id=12345, someField=someField, someOtherField=someOtherField, isElementInA=true), ListCelement(fieldA=2.0, id=12343, someField=someField, someOtherField=someOtherField, isElementInA=false), ListCelement(fieldA=2.0, id=1234566, someField=someField, someOtherField=someOtherField, isElementInA=true), ListCelement(fieldA=2.0, id=11233, someField=someField, someOtherField=someOtherField, isElementInA=false)]