BL
U

37. Union and Intersection of Two Sorted Arrays

Easy

Problem Description

Given two sorted arrays AA (size NN) and BB (size MM), find their sorted union (all distinct elements appearing in either) and intersection (all distinct elements appearing in both).

Input Format

  • •Line 1: Two space-separated integers NN and MM (1≤N,M≤1051 \le N, M \le 10^5).
  • •Line 2: NN sorted integers A1,…,ANA_1, \dots, A_N.
  • •Line 3: MM sorted integers B1,…,BMB_1, \dots, B_M.

Output Format

  • •Line 1: Space-separated distinct integers in Union.
  • •Line 2: Space-separated distinct integers in Intersection, or EMPTY if intersection is empty.
Example 1:
Input:
5 4
1 2 2 3 4
2 2 4 6
Output:
1 2 3 4 6
2 4
Explanation: Union is {1, 2, 3, 4, 6}. Common elements are {2, 4}.
Example 2:
Input:
3 3
1 2 3
4 5 6
Output:
1 2 3 4 5 6
EMPTY
Explanation: Disjoint arrays have empty intersection.
Example 3:
Input:
2 2
5 5
5 5
Output:
5
5
Explanation: Only element 5 in both.
Constraints:
  • Standard integer bounds: 32-bit signed integer or input range [1, 10^5].
  • Time complexity target: O(N) or O(N log N) where applicable.
  • Auxiliary space target: O(1) or minimal auxiliary memory.
Follow up:Can this algorithm be adapted to an online streaming setting where the entire input cannot be held in memory simultaneously?
1,180 Online