DATA STRUCTURES • ALGORITHMS

Union of Two Sorted Arrays

Given two sorted arrays, find their union. The union should contain unique elements from both arrays in sorted order.

Time

O(N + M)

Space

O(1) (excluding result array)

Key Principle 1

Use two pointers approach

Key Principle 2

Handle duplicates while adding to union

Key Principle 3

Efficient linear merge style scan

Key Principle 4

Requires sorted input arrays

UNION_LAB
Current Step
Goal: Merge two sorted arrays into a single union set. Using two pointers.
Playback
Pointers Monitor ⠿
arr1[i]1
arr2[j]2
Union Logic ⠿
1int i = 0, j = 0;
2while (i < n && j < m) {
3    if (arr1[i] < arr2[j]) add(arr1[i++]);
4    else if (arr2[j] < arr1[i]) add(arr2[j++]);
5    else { add(arr1[i++]); j++; }
6}
7while (i < n) add(arr1[i++]);
8while (j < m) add(arr2[j++]);
Array 1 (Sorted)
1
PTR
2
[1]
4
[2]
5
[3]
6
[4]
Array 2 (Sorted)
2
PTR
3
[1]
5
[2]
7
[3]
Union Set (Result)
Union is empty...

Loading Lab...

Union Of Arrays

Union Of Arrays

Union of Two Sorted Arrays

Union of Two Sorted Arrays