How to find union of two sorted array ?

[Question]: In a given two sorted array find union elements. Output should be sorted.
For example : arr1[] = {1,2,3,4,5} arr2[] = {2,3,4,4,5} Output: {1,2,3,4,5}
Approach #1: Use Dictionary / Hashset & after it sort the array which SC: O(m+n) TC: O( (m+n)log(m+n) 
Approach #2: Two pointer approach: use two pointer i & j & fill the elements if first array index is lesser fill it first otherwise fill from another array

func unionOfTwoSortedArray(array1: [Int], array2: [Int]) -> [Int] {
    let firstLength = array1.count
    let secondLength = array2.count
    var i = 0, j = 0
    var unionArray: [Int] = []
    
    while i < firstLength && j < secondLength {
        if array1[i] < array2[j] {
            // To check if unionArray is non empty & elements is not present already
            if unionArray.isEmpty || unionArray.last != array1[i] {
                unionArray.append(array1[i])
            }
            i+=1
        } else {
            if unionArray.isEmpty || unionArray.last != array2[j] {
                unionArray.append(array2[j])
            }
            j+=1
        }
    }
    while i < firstLength {
        if unionArray.last != array1[i] {
            unionArray.append(array1[i])
        }
        i+=1
    }
    while j < secondLength {
        if unionArray.last != array2[j] {
            unionArray.append(array2[j])
        }
        j+=1
    }
    return unionArray
}

let firstArray = [1,2,3,4,5]
let secondArray = [2,3,4,4,5]

let unionArray = unionOfTwoSortedArray(array1: firstArray, array2: secondArray)
print("union-Array->", unionArray)// O/P: [1,2,3,4,5]

Leave a Comment

Your email address will not be published. Required fields are marked *