AlgoViz
HomeArrays & Hashing

Union of two sorted arrays

Easy

Merge two sorted lists, skipping repeats

Problem

Given two sorted arrays nums1 and nums2, return an array that contains the union of these two arrays. The elements in the union must be in ascending order. The union of two arrays is an array where all values are distinct and are present in either the first array, the second array, or both.

In simple words

Walk both sorted lists together, adding each new value once, skipping repeats.

The idea

Walk both arrays with one pointer each, always advancing the one pointing at the smaller value and appending it unless it duplicates the last value written. Sortedness is what lets duplicates be detected by looking only at the previous output.

The trick

  • Advance both pointers when the values are equal — append the value once.
  • Compare against the last appended value to skip duplicates.
  • O(n + m) with no hash set needed.

This one walks through the worked example rather than tracing the algorithm frame by frame — a full walkthrough is still to be drawn. The code and the idea below are the real solution.

1
2
3
4
5
0
1
2
3
4

Step 1 of 2. Here's the example — nums1 = [1, 2, 3, 4, 5], nums2 = [1, 2, 7] Values: 1, 2, 3, 4, 5.

1/2
Optimal
timeO(n+m)spaceO(1) extra
1i = j = 0; res = []2while i < n and j < m:3  if a[i] <= b[j]: v = a[i++]4  else:            v = b[j++]5  if res.empty or res.last != v: res.push(v)6// push remaining of a, then b (skipping duplicates)

Input

array
[1, 2, 3, 4, 5]

Output

answer
—

Check yourself

3 quick questions about this walkthrough. A wrong answer costs nothing.

Examples

Example 1

Input:
a = [1, 2, 3], b = [2, 3, 4]
Output:
[1, 2, 3, 4]
Explanation:
Combine and keep each value once.

Example 2

Input:
a = [1, 1, 2], b = [2, 3]
Output:
[1, 2, 3]
Explanation:
Duplicates collapse to a single copy.

Example 3

Input:
a = [5], b = [5]
Output:
[5]
Explanation:
Both hold 5, so the union is just [5].

Constraints

  • 1 <= nums1.length, nums2.length <= 1000
  • -10^4 <= nums1[i] , nums2[i] <= 10^4
  • Both nums1 and nums2 are sorted in non-decreasing order

Practice this problem:GeeksforGeeks(opens in a new tab)

Finished the walkthrough? Add it to your streak.