Union of Two Sorted Arrays

122.2k
0

Given two sorted integer arrays nums1 and nums2, find their union.

The union contains all distinct elements that are present in either nums1 or nums2.

Return the union array in sorted order.

Example 1

Input: nums1 = [1, 2, 2, 3, 4], nums2 = [2, 4, 6]

Output: [1, 2, 3, 4, 6]

Explanation: The union contains all unique elements from both arrays.

Example 2

Input: nums1 = [1, 1, 2], nums2 = [2, 3, 3]

Output: [1, 2, 3]

Explanation: Duplicate values are included only once in the union.

Brute Force Approach

The direct method builds the union one value at a time. Before adding a value, a linear search checks whether the same value already exists inside unionResult.

Processing both arrays guarantees coverage of every value, while the repeated search prevents duplicate insertion. Since values from nums2 may be smaller than values already collected from nums1, sorting unionResult at the end ensures the required output order.

Algorithm

  • Store the sizes of nums1 and nums2. If both arrays are empty, return an empty array because no values are available for the union.

  • Create an empty unionResult to collect distinct values from both arrays.

  • Traverse nums1 from left to right and search unionResult for the current value. Append it only when it has not been stored earlier, preventing duplicate entries.

  • Traverse nums2 in the same way, checking each value against unionResult before adding it.

  • Sort unionResult after both arrays have been processed, since collecting all values from nums1 before nums2 does not guarantee that the result remains sorted.

  • Return unionResult, which now contains every distinct value from both arrays in sorted order.

Dry Run

Union of Two Arrays Brute Force Dry Run.png

Union of Two Arrays Brute Force Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> findUnion(vector<int>& nums1, vector<int>& nums2) {
vector<int> unionResult;
/*
* Add a value only if it has not
* already been stored in the union.
*/
auto addIfUnique = [&](int value) {
for (int storedValue : unionResult) {
if (storedValue == value) {
return;
}
}
unionResult.push_back(value);
};
for (int value : nums1) {
addIfUnique(value);
}
for (int value : nums2) {
addIfUnique(value);
}
// Restore sorted order after collecting both arrays.
sort(unionResult.begin(), unionResult.end());
return unionResult;
}
};
int main() {
vector<int> nums1 = {1, 1, 2, 3, 4};
vector<int> nums2 = {2, 3, 5, 6};
Solution solution;
vector<int> answer = solution.findUnion(nums1, nums2);
for (int value : answer) {
cout << value << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O((N + M)²), where N and M are the sizes of the two arrays. Each input value may require a linear search through the result, while final sorting takes O(U log U) for U distinct values. The quadratic search dominates in the worst case.

Space Complexity: O(1) auxiliary space when the returned unionResult is excluded.

Better Approach

A set naturally prevents duplicate storage. Inserting every value from both arrays into a set therefore creates the union without requiring a separate linear search before each insertion.

An ordered set maintains values in sorted order automatically. A language providing only an unordered set can store all distinct values first and sort the converted result afterward.

Algorithm

  • Store the sizes of nums1 and nums2. If both arrays are empty, return an empty array.

  • Create unionSet, which stores each distinct value only once and therefore removes duplicates automatically.

  • Traverse nums1 and insert every value into unionSet, where repeated values do not create additional entries.

  • Traverse nums2 and insert its values into the same set, combining the distinct elements of both arrays.

  • Convert the set into unionResult. If the set maintains sorted order, traverse it directly; otherwise, sort the collected values afterward.

  • Return unionResult as the sorted union of the two arrays.

Dry Run

Union of Two Arrays Better Approach Dry Run.png

Union of Two Arrays Better Approach Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> findUnion(vector<int>& nums1, vector<int>& nums2) {
set<int> unionSet;
// A set keeps only one copy of each value.
for (int value : nums1) {
unionSet.insert(value);
}
for (int value : nums2) {
unionSet.insert(value);
}
/*
* Ordered-set traversal already gives
* the values in sorted order.
*/
vector<int> unionResult(
unionSet.begin(),
unionSet.end()
);
return unionResult;
}
};
int main() {
vector<int> nums1 = {1, 1, 2, 3, 4};
vector<int> nums2 = {2, 3, 5, 6};
Solution solution;
vector<int> answer = solution.findUnion(nums1, nums2);
for (int value : answer) {
cout << value << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O((N + M) log(N + M)) in the ordered-set implementation, because inserting each value may require logarithmic time.

Space Complexity: O(N + M) auxiliary space because the set may contain every input value when all values are distinct. The returned array is excluded.

Optimal Approach

Both arrays already contain values in sorted order. Two pointers can therefore merge both arrays while always processing the smallest unprocessed value.

When one current value is smaller, the corresponding pointer moves forward. Equal current values contribute only one union entry, so both pointers move together. Comparing every candidate with the final value inside unionResult prevents duplicates within either input array.

Algorithm

  • Store the sizes N and M, create an empty unionResult, and initialize pointers i = 0 and j = 0 to track the next unprocessed values in both arrays.

  • While both pointers are valid, compare nums1[i] and nums2[j] so the smaller unprocessed value can be handled first.

  • If one value is smaller, select it and move its pointer forward. If both values are equal, select the value once and move both pointers because that value has been processed in both arrays.

  • Append the selected value only when unionResult is empty or its last stored value is different, preventing duplicates from entering the result.

  • After one array is exhausted, process the remaining elements of the other array while applying the same duplicate check.

  • Return unionResult after both arrays have been completely processed.

Dry Run

Union of Two Arrays Optimal Approach Dry Run.png

Union of Two Arrays Optimal Approach Dry Run.png

Solution

#include <bits/stdc++.h>
using namespace std;
class Solution {
public:
vector<int> findUnion(vector<int>& nums1, vector<int>& nums2) {
int n = nums1.size();
int m = nums2.size();
int i = 0;
int j = 0;
vector<int> unionResult;
/*
* Process the smaller current value first
* because both arrays are already sorted.
*/
while (i < n && j < m) {
int currentValue;
if (nums1[i] < nums2[j]) {
currentValue = nums1[i];
i++;
}
else if (nums1[i] > nums2[j]) {
currentValue = nums2[j];
j++;
}
else {
currentValue = nums1[i];
i++;
j++;
}
/*
* Add the value only when it differs
* from the last value already stored.
*/
if (unionResult.empty() ||
unionResult.back() != currentValue) {
unionResult.push_back(currentValue);
}
}
// Process values left in the first array.
while (i < n) {
if (unionResult.empty() ||
unionResult.back() != nums1[i]) {
unionResult.push_back(nums1[i]);
}
i++;
}
// Process values left in the second array.
while (j < m) {
if (unionResult.empty() ||
unionResult.back() != nums2[j]) {
unionResult.push_back(nums2[j]);
}
j++;
}
return unionResult;
}
};
int main() {
vector<int> nums1 = {1, 1, 2, 3, 4};
vector<int> nums2 = {2, 3, 5, 6};
Solution solution;
vector<int> answer = solution.findUnion(nums1, nums2);
for (int value : answer) {
cout << value << " ";
}
return 0;
}

Complexity Analysis

Time Complexity: O(N + M), because each pointer moves through its corresponding array at most once.

Space Complexity: O(1) auxiliary space when the returned union array is excluded.

FAQs

Q1. Why must every value appear only once in the union?

A union represents the set of values appearing in either input array. Sets contain no duplicate entries.

Q2. Why does the Brute Force Approach require final sorting?

Processing all values from nums1 before nums2 can place a smaller nums2 value after larger nums1 values. Final sorting restores the required order.

Q3. Why does the Better Approach use an ordered set?

An ordered set removes duplicates and maintains sorted order during insertion. An unordered set requires final sorting after conversion.

Q4. Why does the Optimal Approach move both pointers after equal values appear?

The shared value has been processed for both arrays and requires only one result entry. Moving both pointers avoids unnecessary repeated comparison.

Q5. How are duplicates inside one input array removed?

Every candidate receives comparison with the final value already stored inside unionResult. An equal candidate receives no additional insertion.

Q6. What happens when one input array is empty?

The result contains the distinct values from the non-empty array in sorted order.

ArraysTwo Pointer

Read Similar Blogs

Arrays

Row wise traversal

Given a matrix with N rows and M columns, print all elements row by row from left to right. Input: mat = [[1, 2, 3], [4, 5, 6]] Output: 1 2 3 4 5 6 Explanation: First row prints as 1 2 3 , then sec...

61.7k
Arrays

Main Diagonal Print

Given a matrix with N rows and M columns, print all elements present on the main diagonal. Input: mat = [[1, 2, 3], [4, 5, 6], [7, 8, 9]] Output: 1 5 9 Explanation: Main diagonal cells are mat[0][0...

67.1k
Arrays

Search Element in Matrix

Input: mat = [[1, 2, 3], [7, 6, 8], [9, 2, 5]], X = 6 Output: {1, 1} Explanation: Target value 6 is present at row 1 and column 1 . Input: mat = [[3, 4, 5, 0], [2, 9, 8, 7]], X = 10 Output: {-1, -1...

98.5k
Comments0