Problem Statement
Given two sorted arrays nums1 and nums2, return an array that contains the union of these two arrays. The elements in the union must be in ascending order.
The union of two arrays is an array where all values are distinct and are present in either the first array, the second array, or both.
LeetCode:
Examples
Example 1:
Input: nums1 = [1, 2, 3, 4, 5], nums2 = [1, 2, 7]
Output: [1, 2, 3, 4, 5, 7]
Exaplanation: The elements 1, 2 are common to both, 3, 4, 5 are from nums1
and 7 is from nums2.Example 2:
Input: nums1 = [3, 4, 6, 6, 9, 9], nums2 = [1, 2, 6, 9, 9]
Output: [1, 2, 3, 4, 6, 9]
Explanation: The elements 6, 9 is common to both.Example 3:
Input: nums1 = [3, 4, 4], nums2 = [6, 7, 7]
Output: [3, 4, 6, 7]
Explanation: There are no common elements in arrays however there are 4, 7 duplicates in nums1 and nums2 respectively.Different Approaches
1️⃣ Brute Force Approach
Intuition:
The union of two arrays will be all the unique elements of both of the arrays combined. So, using a set data structure will help & can find the distinct elements because the set does not hold any duplicates. As it is mandatory to preserve the order of the elements, use an ordered set.
Approach:
- Declare a set s to store all the unique elements and a vector or list union to store the final answer.
- Iterate through nums1 and nums 2 to store the elements in the set.
- Now, iterate in the set and copy all the elements of the set to the answer vector and return it.
Code:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> unionArray(vector<int>& nums1, vector<int>& nums2) {
// Using unordered for storing unique elements
set<int> s;
vector<int> Union;
// Insert all elements of nums1 into the set
for (int num : nums1) {
s.insert(num);
}
// Insert all elements of nums2 into the set
for (int num : nums2) {
s.insert(num);
}
// Convert the set to vector to get the union
for (int num : s) {
Union.push_back(num);
}
return Union;
}
};
int main() {
// Initialize the arrays
vector<int> nums1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<int> nums2 = {2, 3, 4, 4, 5, 11, 12};
// Create an instance of the Solution class
Solution finder;
/* Get the union of nums1 and
nums2 using the class method*/
vector<int> Union = finder.unionArray(nums1, nums2);
// Output the result
cout << "Union of nums1 and nums2 is:" << endl;
for (int val : Union) {
cout << val << " ";
}
cout << endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
O( (M+N)log(M+N) ), at max set can store M+N elements {when there are no common elements and elements in nums1 , nums2 are distinct}. So InsertingM+N thelement takeslog(M+N)time. Upon approximation across inserting all elements in worst, it would takeO((M+N)log(M+N)time. - Space Complexity:
O(M+N), considering space of Union Array.
2️⃣ Optimal Approach
The algorithm to merge two sorted arrays efficiently is a classic technique commonly known as the “Merge” algorithm. The idea is to start from the beginning of both arrays, compare the elements, and insert the smaller one into a new array. This process is repeated until all elements from both arrays are merged into the final sorted array.
Intuition:
The optimal approach uses the two-pointers to solve the problem. Use two pointers, one for each array, and traverse both arrays simultaneously. Keep adding the smaller element between the two arrays to the result vector if it hasn't been added already.
What if both elements are equal?
If both elements are equal, add any one of them, ensuring that all unique elements are added in sorted order.
Approach:
- Initialize two variable
ito iteratenums1andjto iteratenums2as0. - Create an empty vector for storing the
unionofnums1andnums2. - If current element of
nums1is equal to current element ofnums2, this means its a common element, so insert only one element in theunion& increment it by1. - If current element of
nums1is less than current element ofnums2, insert current element ofnums1inunion. Also check if last element inunionvector is not equal tonums1[ i ], then insert in union else don’t insert. After checking incrementi. - If current element of
nums1is greater than current element ofnums2, insert current element ofnums2in union. Similar to last point, check if the last element in the union vector is not equal tonums2[ j ], then insert in the union, else don’t insert. After checking incrementj.
Dry Run:
Initialization:
+-----+-----+-----+------+------+
nums1 = | 1 | 1 | 2 | 7 | 7 |
+-----+-----+-----+------+------+
0 1 2 3 4
^
|
i
+-----+-----+-----+
nums2 = | 2 | 7 | 9 |
+-----+-----+-----+
0 1 2
^
|
j
+---------+
newArry = | empty |
+---------+First Iteration:
+-----+-----+-----+------+------+
nums1 = | 1 | 1 | 2 | 7 | 7 |
+-----+-----+-----+------+------+
0 1 2 3 4
^
|
i
+-----+-----+-----+
nums2 = | 2 | 7 | 9 |
+-----+-----+-----+
0 1 2
^
|
j
nums1[i] <= nums2[j] && ans is empty
Hence, add nums[i] in ans.
Increment i by 1.
+-----+
newArr = | 1 |
+-----+
+-----+-----+-----+------+------+
nums1 = | 1 | 1 | 2 | 7 | 7 |
+-----+-----+-----+------+------+
0 1 2 3 4
^
|
i
+-----+-----+-----+
nums2 = | 2 | 7 | 9 |
+-----+-----+-----+
0 1 2
^
|
jSecond Iteration:
+-----+-----+-----+------+------+
nums1 = | 1 | 1 | 2 | 7 | 7 |
+-----+-----+-----+------+------+
0 1 2 3 4
^
|
i
+-----+-----+-----+
nums2 = | 2 | 7 | 9 |
+-----+-----+-----+
0 1 2
^
|
j
+-----+
newArr = | 1 |
+-----+
nums1[i] <= nums2[j] && newArr.back() != nums1[i]
1 == 2 && 1 != 1
false
Increment i by 1.
+-----+
newArr = | 1 |
+-----+
+-----+-----+-----+------+------+
nums1 = | 1 | 1 | 2 | 7 | 7 |
+-----+-----+-----+------+------+
0 1 2 3 4
^
|
i
+-----+-----+-----+
nums2 = | 2 | 7 | 9 |
+-----+-----+-----+
0 1 2
^
|
jThird Iteration:
+-----+-----+-----+------+------+
nums1 = | 1 | 1 | 2 | 7 | 7 |
+-----+-----+-----+------+------+
0 1 2 3 4
^
|
i
+-----+-----+-----+
nums2 = | 2 | 7 | 9 |
+-----+-----+-----+
0 1 2
^
|
j
+-----+
newArr = | 1 |
+-----+
nums1[i] <= nums2[j] && ans.back() != nums1[i]
2 <= 2 && 1 != 2
true
ans.push_back(nums[i])
Increment i by 1.
+-----+-----+
newArr = | 1 | 2 |
+-----+-----+
+-----+-----+-----+------+------+
nums1 = | 1 | 1 | 2 | 7 | 7 |
+-----+-----+-----+------+------+
0 1 2 3 4
^
|
i
+-----+-----+-----+
nums2 = | 2 | 7 | 9 |
+-----+-----+-----+
0 1 2
^
|
jCode:
#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> unionArray(vector<int>& nums1, vector<int>& nums2) {
vector<int> Union; // Vector to store the union elements
int i = 0, j = 0;
int n = nums1.size();
int m = nums2.size();
while (i < n && j < m) {
// Case 1 and 2
if (nums1[i] <= nums2[j]){
if (Union.size() == 0 || Union.back() != nums1[i])
Union.push_back(nums1[i]);
i++;
}
//case 3
else {
if (Union.size() == 0 || Union.back() != nums2[j])
Union.push_back(nums2[j]);
j++;
}
}
// If any element left in arr1
while (i < n){
if (Union.back() != nums1[i])
Union.push_back(nums1[i]);
i++;
}
// If any elements left in arr2
while (j < m){
if (Union.back() != nums2[j])
Union.push_back(nums2[j]);
j++;
}
return Union;
}
};
int main() {
vector<int> nums1 = {1, 2, 3, 4, 5, 6, 7, 8, 9, 10};
vector<int> nums2 = {2, 3, 4, 4, 5, 11, 12};
// Create an instance of the Solution class
Solution finder;
// Get union of nums1 and nums2 using class method
vector<int> Union = finder.unionArray(nums1, nums2);
cout << "Union of nums1 and nums2 is:" << endl;
for (int val : Union) {
cout << val << " ";
}
cout << endl;
return 0;
}
Complexity Analysis:
- Time Complexity:
O(M+N)because at max i runs for N times and j runs for M times. When there are no common elements in arr1 and arr2 and all elements in arr1, arr2 are distinct. - Space Complexity: The space complexity is
O(m + n)as well, as we are creating a new array to store the merged result. The space required is directly proportional to the sum of the lengths of the input arrays.