ArrayProblem 6 of 36
Find the Union and Intersection of the two sorted arrays
Problem Statement
Given two sorted arrays, find their union and intersection.
- Union: All distinct elements present in either array
- Intersection: All elements present in both arrays
Example:
- Input:
arr1 = [1, 2, 3, 4, 5],arr2 = [2, 3, 4, 4, 5, 6] - Union:
[1, 2, 3, 4, 5, 6] - Intersection:
[2, 3, 4, 5]
Union of Two Sorted Arrays
Approach 1: Using Set (Brute Force)
Intuition
Insert all elements from both arrays into a set to automatically handle duplicates.
Algorithm
- Create an ordered set (
TreeSet) - Insert all elements of first array
- Insert all elements of second array
- Convert set to result list
java
import java.util.*;
public class Solution {
public List<Integer> findUnion(int[] arr1, int[] arr2) {
Set<Integer> set = new TreeSet<>();
for (int num : arr1) {
set.add(num);
}
for (int num : arr2) {
set.add(num);
}
return new ArrayList<>(set);
}
}Complexity Analysis
- Time Complexity: O((m + n) log(m + n)) - Due to set insertions
- Space Complexity: O(m + n) - Set storage
Approach 2: Two Pointers (Optimal)
Intuition
Use two pointers to traverse both sorted arrays simultaneously. Compare elements and add the smaller one to result, skipping duplicates.
Algorithm
- Initialize
i = 0,j = 0 - Compare
arr1[i]andarr2[j] - Push smaller (or equal) value once, move pointer(s)
- Skip duplicates while moving pointers
- Add remaining unique elements
java
import java.util.*;
public class Solution {
public List<Integer> findUnion(int[] arr1, int[] arr2) {
List<Integer> result = new ArrayList<>();
int i = 0, j = 0;
int m = arr1.length, n = arr2.length;
while (i < m && j < n) {
// Skip duplicates in arr1
while (i > 0 && i < m && arr1[i] == arr1[i - 1]) i++;
// Skip duplicates in arr2
while (j > 0 && j < n && arr2[j] == arr2[j - 1]) j++;
if (i >= m || j >= n) break;
if (arr1[i] < arr2[j]) {
result.add(arr1[i]);
i++;
} else if (arr1[i] > arr2[j]) {
result.add(arr2[j]);
j++;
} else {
result.add(arr1[i]);
i++;
j++;
}
}
// Add remaining elements from arr1
while (i < m) {
if (i == 0 || arr1[i] != arr1[i - 1]) {
result.add(arr1[i]);
}
i++;
}
// Add remaining elements from arr2
while (j < n) {
if (j == 0 || arr2[j] != arr2[j - 1]) {
result.add(arr2[j]);
}
j++;
}
return result;
}
}Complexity Analysis
- Time Complexity: O(m + n) - Single pass through both arrays
- Space Complexity: O(1) - Excluding output array
Intersection of Two Sorted Arrays
Approach 1: Using HashMap (Brute Force)
Intuition
Store frequency of elements from first array, then check against second array.
Algorithm
- Build frequency map of first array
- Traverse second array
- If frequency of current element is > 0, add to answer
- Decrement frequency
java
import java.util.*;
public class Solution {
public List<Integer> findIntersection(int[] arr1, int[] arr2) {
Map<Integer, Integer> freq = new HashMap<>();
List<Integer> result = new ArrayList<>();
for (int num : arr1) {
freq.put(num, freq.getOrDefault(num, 0) + 1);
}
for (int num : arr2) {
if (freq.getOrDefault(num, 0) > 0) {
result.add(num);
freq.put(num, freq.get(num) - 1);
}
}
return result;
}
}Complexity Analysis
- Time Complexity: O(m + n) - Two passes
- Space Complexity: O(min(m, n)) - HashMap storage
Approach 2: Two Pointers (Optimal)
Intuition
Since arrays are sorted, use two pointers. When elements are equal, add to result and move both pointers.
Algorithm
- Initialize two pointers at start of arrays
- If
arr1[i] < arr2[j], incrementi - If
arr1[i] > arr2[j], incrementj - If equal, add element and move both pointers
- Stop when any pointer reaches the end
java
import java.util.*;
public class Solution {
public List<Integer> findIntersection(int[] arr1, int[] arr2) {
List<Integer> result = new ArrayList<>();
int i = 0, j = 0;
int m = arr1.length, n = arr2.length;
while (i < m && j < n) {
if (arr1[i] < arr2[j]) {
i++;
} else if (arr1[i] > arr2[j]) {
j++;
} else {
result.add(arr1[i]);
i++;
j++;
}
}
return result;
}
}Dry Run Example
arr1 = [1, 2, 3, 4, 5]
arr2 = [2, 3, 4, 4, 5, 6]
Step 1: arr1[0]=1 < arr2[0]=2, i++
i=1, j=0
Step 2: arr1[1]=2 == arr2[0]=2, add 2
i=2, j=1, result=[2]
Step 3: arr1[2]=3 == arr2[1]=3, add 3
i=3, j=2, result=[2,3]
Step 4: arr1[3]=4 == arr2[2]=4, add 4
i=4, j=3, result=[2,3,4]
Step 5: arr1[4]=5 > arr2[3]=4, j++
i=4, j=4
Step 6: arr1[4]=5 == arr2[4]=5, add 5
i=5, j=5, result=[2,3,4,5]
i >= m, STOP
Intersection: [2, 3, 4, 5]
Complexity Analysis
- Time Complexity: O(m + n) - Single pass through both arrays
- Space Complexity: O(1) - Excluding output array
Key Takeaways
- Two-pointer technique leverages the sorted property for O(m + n) time
- For unsorted arrays, consider sorting first or using hash-based approaches
- Handle duplicates carefully based on problem requirements
- The sorted property eliminates the need for extra space (hash tables)
- Union is similar to merge step in merge sort
- Intersection can also be solved using binary search (O(m log n)) when one array is much smaller