Two Sorted Lists Union | Dataford Interview Questions

Hopper may receive sorted lists of fare identifiers from two search sources. Given two sorted integer lists, return their union: every distinct value appearing in either list, in ascending order.

Implement merge_sorted_union(list1, list2) using the sorted order of the inputs. Duplicate values within one list or across both lists must appear only once in the result.

Formal Specification

Input: Two lists list1 and list2 of integers, each sorted in nondecreasing order. Either list may be empty.
Output: A new list containing each distinct integer from either input exactly once, sorted in ascending order.
Do not modify either input list.

Constraints

0 <= len(list1), len(list2) <= 10^5
-10^9 <= list1[i], list2[i] <= 10^9
Both input lists are sorted in nondecreasing order
The output contains each distinct value exactly once

Function Signature

def merge_sorted_union(list1, list2):

Your question is Two Sorted Lists Union. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem