Intersection of two Sorted Array in Kotlin

by

To find the intersection of two sorted arrays, you can use the following algorithm:

  1. Initialize two pointers, one for each array, pointing to the first element of the array.
  2. Loop through the arrays until either pointer reaches the end of its respective array.
  3. Compare the values of the elements pointed to by the two pointers. If they are equal, add the value to the result array and increment both pointers.
  4. If the value pointed to by the first pointer is less than the value pointed to by the second pointer, increment the first pointer.
  5. If the value pointed to by the second pointer is less than the value pointed to by the first pointer, increment the second pointer.
  6. Continue the loop until either pointer reaches the end of its respective array.
  7. Return the result array containing the common elements.

The time complexity of this algorithm is O(m + n), where m and n are the lengths of the two arrays.

here’s an implementation of the algorithm in Kotlin:

Kotlin
fun intersection(arr1: IntArray, arr2: IntArray): IntArray {
    val result = mutableListOf<Int>()
    var i = 0
    var j = 0
    while (i < arr1.size && j < arr2.size) {
        when {
            arr1[i] == arr2[j] -> {
                result.add(arr1[i])
                i++
                j++
            }
            arr1[i] < arr2[j] -> i++
            else -> j++
        }
    }
    return result.toIntArray()
}
fun main() {
    val arr1 = intArrayOf(1, 2, 3, 4, 5, 6)
	val arr2 = intArrayOf(4, 5, 6, 7, 8)
	println(intersection(arr1, arr2).contentToString())   // Output: [4, 5, 6]
}

here are the steps involved in the intersection function in Kotlin:

  1. Create a new function named intersection that takes two sorted integer arrays as input and returns an integer array containing the common elements of the two input arrays.
  2. Create a mutable list of integers named result to store the common elements found in the two input arrays.
  3. Initialize two integer variables i and j to 0. These variables will be used as pointers to traverse the input arrays.
  4. Use a while loop to traverse the input arrays as long as the pointers i and j are within their respective array bounds.
  5. Use a when expression to compare the values at the current indices of the input arrays pointed to by the i and j pointers.
  6. If the values are equal, add the common element to the result list, and increment both pointers.
  7. If the value in the first array is less than the value in the second array, increment the pointer for the first array.
  8. If the value in the second array is less than the value in the first array, increment the pointer for the second array.
  9. After the while loop is complete, convert the result list of common elements to an IntArray and return it.
  10. The intersection function is now complete and can be used to find the intersection of two sorted integer arrays.

Leave a Comment