Merge two sorted arrays into distinct values

Two integer arrays, nums1 and nums2, are each sorted in non-decreasing order and may contain repeated values. Return one array, sorted in ascending order, that contains every value appearing in either input exactly once.

def merge_unique(nums1: list[int], nums2: list[int]) -> list[int]: ...

Aim for time linear in the total input size. Do not just concatenate and sort.

Constraints

• 0 <= len(nums1), len(nums2) <= 10^5
• -10^9 <= nums1[i], nums2[i] <= 10^9
• Each input is sorted in non-decreasing order.

Example 1

nums1 = [0, 4, 4, 9]
nums2 = [-3, 4, 8, 9, 9]
output: [-3, 0, 4, 8, 9]

The value 4 repeats inside nums1 and also appears in nums2. The value 9 appears in both arrays and repeats in nums2. Each one appears once in the output.

Example 2

nums1 = []
nums2 = [5, 5, 5]
output: [5]

Be ready for follow-ups. One asks you to write the result into nums1 using O(1) extra space. Another asks you to merge k sorted inputs.

Reconstructed from the reported question; details may differ from what interviewers ask.