[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]