DSA interview question

Union of Two Sorted Arrays

Easy · Algorithms · Topics: array, two pointer

The problem

Two regional warehouses each send a sorted list of the product IDs they stock, and head office wants a single sorted list of every distinct ID stocked by either warehouse. The lists can each hold a million IDs and may contain repeats. Throwing everything into a set works but costs O((n + m) log(n + m)) and extra memory. Because both inputs are already sorted, a two-pointer merge produces the union in one linear pass, skipping duplicates as it goes. It's the same merge step used in merge sort.

Example: [1, 2, 3, 4, 5] and [1, 2, 3, 6, 7] → [1, 2, 3, 4, 5, 6, 7].

Function signature

vector<int> sortedUnion(const vector<int>& a, const vector<int>& b);  // distinct values, sorted

Test cases

Input `(a, b)`	Output	Explanation
`([1, 2, 3, 4, 5], [1, 2, 3, 6, 7])`	`[1, 2, 3, 4, 5, 6, 7]`
`([2, 2, 3, 4, 5], [1, 1, 2, 3, 4])`	`[1, 2, 3, 4, 5]`	Duplicates inside each array
`([1, 1, 1], [1])`	`[1]`
`([], [3, 3, 4])`	`[3, 4]`	One side empty
`([-5, 0, 10], [-5, -3, 10, 12])`	`[-5, -3, 0, 10, 12]`	Negative values

(Confirm: both inputs are sorted in non-decreasing order; the result has no duplicates.)

How interviewers phrase it

"Find the union of two sorted arrays" (GeeksforGeeks).
Often paired with "find the intersection of two sorted arrays."
A test of the two-pointer merge technique before merge sort or "merge k sorted lists".

Clarifying questions to ask

Are both arrays sorted?
Should the result contain duplicates? (Usually not for a union.)
Can the arrays be empty?
Is extra space for the output fine?

Follow-ups to expect

"Why not use a set?"
"How do you skip duplicates?"
"How would you compute the intersection?"
"What if the arrays were unsorted?"
"Complexity?"

Practise questions like this with a real engineer

On Practick another engineer interviews you live for 60 minutes on a question from this bank. They have the full interviewer guide beside the call: the expected answer to every follow-up, hints to give if you stall, and a scoring rubric. You get the model solution once the session settles. It is free: interview someone for an hour and you have earned your own.

Book a free mock interview