Union and Intersection of Two Sorted Arrays easy
Description
Given two sorted arrays a[] and b[], find their union and intersection.
- Union: All distinct elements present in either array.
- Intersection: All distinct elements present in both arrays.
The result should be in sorted order.
Examples
> Case 1:
Input: a = [1, 2, 3, 4, 5], b = [2, 3, 4, 4, 5, 6]
Union: [1, 2, 3, 4, 5, 6]
Intersection: [2, 3, 4, 5]
> Case 2:
Input: a = [1, 1, 2, 3], b = [2, 2, 4, 5]
Union: [1, 2, 3, 4, 5]
Intersection: [2]Constraints
1 <= a.length, b.length <= 10^5- Arrays are sorted in non-decreasing order
Approach: Two Pointers (Merge-Like)
Since both arrays are sorted, we can use a technique similar to the merge step of merge sort. Two pointers walk through both arrays simultaneously.
Code
Explanation
Union: Walk both pointers forward. At each step, take the smaller element. If both are equal, take it once and advance both. Skip duplicates within each array.
Intersection: Walk both pointers forward. Only add to the result when both point to equal elements. If one is smaller, advance that pointer to “catch up.”
This is the same merge logic used in merge sort, adapted to produce union/intersection instead of a fully merged array.
Why not just use sets? Sets work, but the two-pointer approach: (1) preserves sorted order, (2) uses O(1) extra space (besides the result), and (3) runs in O(n+m) time. A set-based approach is O(n+m) on average but O(n log n) worst-case for tree-based sets, and doesn’t guarantee order.
Analysis
- Time Complexity:
O(n + m)— each pointer moves at most n or m times - Space Complexity:
O(n + m)— for the result array