Union of two Sorted Array in Kotlin

by

To find the union of two sorted arrays, you can use a similar approach as finding the intersection of two sorted arrays. Here’s an algorithm to find the union of two sorted arrays:

  1. Initialize two pointers i and j to 0, which will be used to traverse the two sorted arrays.
  2. Create an empty list result to store the union of the two arrays.
  3. While both pointers i and j are within the bounds of the arrays, do the following:
    1. If arr1[i] is less than arr2[j], add arr1[i] to the result list and increment i.
    2. If arr1[i] is greater than arr2[j], add arr2[j] to the result list and increment j.
    3. If arr1[i] is equal to arr2[j], add either arr1[i] or arr2[j] to the result list and increment both pointers.
  4. If there are any remaining elements in either array after the pointers have reached the end of the arrays, add those elements to the result list.
  5. Convert the result list to an array and return it.

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

Here’s an example implementation of the above algorithm in Kotlin:

Kotlin
fun union(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++
            }
            arr1[i] > arr2[j] -> {
                result.add(arr2[j])
                j++
            }
            else -> {
                result.add(arr1[i])
                i++
                j++
            }
        }
    }
    while (i < arr1.size) {
        result.add(arr1[i])
        i++
    }
    while (j < arr2.size) {
        result.add(arr2[j])
        j++
    }
    return result.toIntArray()
}
fun main(){
    val arr1 = intArrayOf(1, 2, 3, 4, 5, 6)
	val arr2 = intArrayOf(4, 5, 6, 7, 8)
	println(union(arr1, arr2).contentToString()) // Output: [1, 2, 3, 4, 5, 6, 7, 8]
}

To find the union of two sorted arrays:

  1. Initialize two pointers i and j to 0, which will be used to traverse the two sorted arrays.This step sets up two pointers that will be used to track the current position in each of the two input arrays.
  2. Create an empty list result to store the union of the two arrays.The result list will be used to store the elements that are present in either or both of the input arrays.
  3. While both pointers i and j are within the bounds of the arrays, do the following:This step sets up a loop that will run until we have reached the end of both arrays.
  4. If arr1[i] is less than arr2[j], add arr1[i] to the result list and increment i.If the element at the current position in arr1 is smaller than the element at the current position in arr2, it means that the element at arr1[i] is not present in arr2, so we add it to the result list. We then increment the i pointer to move to the next element in arr1.
  5. If arr1[i] is greater than arr2[j], add arr2[j] to the result list and increment j.If the element at the current position in arr1 is greater than the element at the current position in arr2, it means that the element at arr2[j] is not present in arr1, so we add it to the result list. We then increment the j pointer to move to the next element in arr2.
  6. If arr1[i] is equal to arr2[j], add either arr1[i] or arr2[j] to the result list and increment both pointers.If the element at the current position in arr1 is equal to the element at the current position in arr2, it means that the element is present in both arrays, so we can add either arr1[i] or arr2[j] to the result list. We then increment both pointers to move to the next elements in both arrays.
  7. If there are any remaining elements in either array after the pointers have reached the end of the arrays, add those elements to the result list.This step handles the case where we have reached the end of one of the input arrays but there are still elements remaining in the other array. In this case, we can simply add the remaining elements to the result list.
  8. Convert the result list to an array and return it.This step converts the result list to an IntArray and returns it.

Overall, the algorithm works by comparing the elements at the current positions in both input arrays and adding the smaller of the two elements to the result list. If the elements are equal, we add either one to the result list. We then increment the pointers for the arrays containing the smaller element. This process continues until we reach the end of both arrays. Any remaining elements in either array are added to the result list. The resulting IntArray contains all the elements that are present in either or both of the input arrays.

Leave a Comment