# Merges two sorted arrays into a single sorted array
# without duplicates.
#
# Example:
# arr1 = [1, 2, 2, 3, 7, 7, 7, 8, 9]
# arr2 = [0, 0, 4, 4, 4, 5, 6, 7, 7, 8]
#
# Result:
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
#
# Time Complexity: O(n + m)
# Space Complexity: O(n + m)
def merge_sorted_unique(arr1, arr2)
result = []
i = 0
j = 0
while i < arr1.length && j < arr2.length
if arr1[i] < arr2[j]
value = arr1[i]
i += 1
elsif arr1[i] > arr2[j]
value = arr2[j]
j += 1
else
# Same value appears in both arrays.
value = arr1[i]
i += 1
j += 1
end
# Add value only if it differs from the last inserted value.
result << value if result.empty? || result.last != value
end
# Process remaining elements from arr1.
while i < arr1.length
value = arr1[i]
i += 1
result << value if result.empty? || result.last != value
end
# Process remaining elements from arr2.
while j < arr2.length
value = arr2[j]
j += 1
result << value if result.empty? || result.last != value
end
result
end
# Example usage
arr1 = [1, 2, 2, 3, 7, 7, 7, 8, 9]
arr2 = [0, 0, 4, 4, 4, 5, 6, 7, 7, 8]
merged = merge_sorted_unique(arr1, arr2)
puts merged.inspect
# run:
#
# [0, 1, 2, 3, 4, 5, 6, 7, 8, 9]
#
