Find the Common in Three Sorted Array in Kotlin

One common approach to finding common elements in three sorted arrays is to use a “merge” strategy, where you compare the elements of the three arrays and find the ones that are common. Here’s a step-by-step algorithm to accomplish this:

1. Initialize three pointers, one for each of the three arrays, starting at the beginning of each array.
2. While all three pointers are still within their respective arrays, do the following:
   • Compare the elements pointed to by the three pointers. If they are all equal, you have found a common element. Add it to a result array or print it out, and advance all three pointers to the next element in each array.
   • If the element pointed to by the first pointer is less than either of the other two elements, advance the first pointer to the next element.
   • If the element pointed to by the second pointer is less than either of the other two elements, advance the second pointer to the next element.
   • If the element pointed to by the third pointer is less than either of the other two elements, advance the third pointer to the next element.
3. When any one of the pointers reaches the end of its respective array, the algorithm is finished. All common elements have been found.

Here’s an example Kotlin code for finding common elements in three sorted arrays:

fun main() {
    val arr1 = intArrayOf(1, 4, 6, 8, 10)
    val arr2 = intArrayOf(2, 4, 5, 6, 10)
    val arr3 = intArrayOf(3, 4, 6, 9, 10)

    val common = findCommonElements(arr1, arr2, arr3)

    if (common.isNotEmpty()) {
        println("Common elements: ${common.contentToString()}")
    } else {
        println("No common elements found.")
    }
}

fun findCommonElements(arr1: IntArray, arr2: IntArray, arr3: IntArray): IntArray {
    var i = 0
    var j = 0
    var k = 0
    val result = mutableListOf<Int>()

    while (i < arr1.size && j < arr2.size && k < arr3.size) {
        when {
            arr1[i] == arr2[j] && arr2[j] == arr3[k] -> {
                result.add(arr1[i])
                i++
                j++
                k++
            }
            arr1[i] < arr2[j] -> i++
            arr2[j] < arr3[k] -> j++
            else -> k++
        }
    }
    return result.toIntArray()
}

1. The function takes three input parameters, arr1, arr2, and arr3, which are arrays of integers. It returns an array of integers that contains the common elements in the three input arrays.
2. The function initializes three variables, i, j, and k, to 0. These variables will be used as pointers to iterate through the three arrays.
3. The function creates an empty mutable list called result, which will be used to store the common elements found in the input arrays.
4. The function enters a while loop that runs as long as i, j, and k are all within the bounds of their respective arrays. Inside the loop, the function performs the following steps:a. It checks if the elements pointed to by i, j, and k are all equal. If they are, it means that the current element is a common element, so it adds the element to the result list and increments all three pointers.b. If the element pointed to by i is less than the element pointed to by j, the function increments i to move to the next element in arr1. This is because, since the arrays are sorted, if arr1[i] is less than arr2[j], arr1[i] cannot be a common element with arr2[j] or any subsequent elements in arr2.c. If the element pointed to by j is less than the element pointed to by k, the function increments j to move to the next element in arr2. This is because, since the arrays are sorted, if arr2[j] is less than arr3[k], arr2[j] cannot be a common element with arr3[k] or any subsequent elements in arr3.d. If none of the above conditions are true, the function increments k to move to the next element in arr3. This is because, since the arrays are sorted, if arr3[k] is less than arr1[i] or arr2[j], arr3[k] cannot be a common element with any subsequent elements in arr1 or arr2.
5. After the while loop exits, the function returns the result list as an integer array by calling the toIntArray() method on the list.

The time complexity of the findCommonElements function is O(n), where n is the total number of elements in the input arrays. This is because the function only iterates through each of the input arrays once, and the running time of each iteration is constant.

The space complexity of the function is also O(n), because the result list can potentially contain all n elements of the input arrays. However, in the worst case scenario where there are no common elements, the result list will be empty, so the space complexity will be O(1).

Overall, this algorithm has a linear time complexity, which is optimal for finding common elements in three sorted arrays.