Union of Two Sorted Arrays
Problem link: https://www.geeksforgeeks.org/problems/union-of-two-sorted-arrays-1587115621/1
Problem Statement
Given two sorted arrays a[] and b[], find the union of these two arrays. The union of two arrays can be defined as the set containing distinct elements from both arrays. The elements in the union should be in sorted order.
Input
Two sorted integer arrays a[] and b[].
Output
An ArrayList of integers representing the union of the two arrays in sorted order.
Example
Input: a[] = [1, 2, 3, 4, 5], b[] = [1, 2, 3, 6, 7] Output: [1, 2, 3, 4, 5, 6, 7] Explanation: Distinct elements from both arrays are 1, 2, 3, 4, 5, 6, 7.
Explanation
We combine elements from both arrays. Elements like 1, 2, and 3 appear in both but are only included once in the result to maintain 'distinct' property.
Brute Force
Intuition
Use a Set data structure (specifically a TreeSet to keep it sorted) to store all elements from both arrays. The set automatically handles duplicates.
Approach
- Initialize a
TreeSet. - Iterate through array
aand add all elements to the set. - Iterate through array
band add all elements to the set. - Convert the set to a list and return.
Dry Run
a=[1,2], b=[2,3] Set: {1, 2} -> {1, 2, 3} Result: [1, 2, 3]
Code (Java)
import java.util.*;
class Solution {
public static ArrayList<Integer> findUnion(int a[], int b[]) {
TreeSet<Integer> set = new TreeSet<>();
for (int x : a) set.add(x);
for (int x : b) set.add(x);
return new ArrayList<>(set);
}
}
Complexity Analysis
Adding elements to a TreeSet takes logarithmic time, and we do this for all elements in both arrays.
Optimal Solution
Intuition
Since the arrays are already sorted, we can use two pointers (one for each array). Compare the elements at both pointers, pick the smaller one, and move that pointer forward. To handle duplicates, only add the element if it is different from the last element added to the result.
Approach
- Initialize
i = 0,j = 0and an empty listunion. - While
i < nandj < m:- If
a[i] <= b[j]: Adda[i]tounion(if not duplicate) andi++. - Else: Add
b[j]tounion(if not duplicate) andj++.
- If
- Add remaining elements from array
aorbwhile checking for duplicates. - Return
union.
Dry Run
a=[1,2,3], b=[2,4]
- i=0, j=0: 1 < 2. Add 1. i=1.
- i=1, j=0: 2 == 2. Add 2. i=2, j=1.
- i=2, j=1: 3 < 4. Add 3. i=3.
- Array a exhausted. j=1: Add 4. j=2. Result: [1, 2, 3, 4]
Code (Java)
Complexity Analysis
We traverse both arrays exactly once. The space complexity is O(1) if we don't count the space required for the output list.
Quick Revision (Brute Force)
- Use TreeSet for uniqueness and sorting
- O((N+M) log (N+M)) time
Quick Revision (Optimal)
- Two-Pointer merge strategy
- Compare a[i] and b[j]
- Add smaller value and check for duplicates with previous entry
- O(N+M) time, O(1) extra space