Practice › Arrays
Union of Two Sorted Arrays
Easy · Arrays · Asked at TCS, Infosys, Wipro, Accenture, Cognizant
Both arrays are sorted in non-decreasing order. Print their union: every distinct value that appears in either array, in increasing order.
Input
First line: n. Second line: the first array. Third line: m. Fourth line: the second array.
Output
The union, space-separated.
Constraints
- 1 ≤ n, m ≤ 10^5
- -10^9 ≤ values ≤ 10^9
Merge with two pointers and skip a value if it equals the last one you printed.
Example 1
Input
5 1 2 3 4 5 3 1 2 7
Output
1 2 3 4 5 7
Example 2
Input
4 1 1 1 1 2 2 2
Output
1 2
Hints
- Walk both arrays with one pointer each, always taking the smaller current value.
- Before printing a value, check that it differs from the last value you printed.
Approach
This is the merge step of merge sort with de-duplication. Pointers i and j start at 0; take the smaller of a[i] and b[j] (take one and advance both when equal). Append a value only if the result is empty or its last element is different. When one array runs out, continue with the other using the same check.
Complexity: O(n + m) time · O(n + m) space for the output
Solution
C++ solution
#include <bits/stdc++.h>
using namespace std;
int main() {
int n, m;
cin >> n;
vector<long long> a(n);
for (auto &x : a) cin >> x;
cin >> m;
vector<long long> b(m);
for (auto &x : b) cin >> x;
vector<long long> u;
auto add = [&](long long v) {
if (u.empty() || u.back() != v) u.push_back(v);
};
int i = 0, j = 0;
while (i < n || j < m) {
if (j == m || (i < n && a[i] <= b[j])) add(a[i++]);
else add(b[j++]);
}
for (size_t k = 0; k < u.size(); k++) cout << u[k] << (k + 1 < u.size() ? " " : "\n");
return 0;
}Python solution
import sys
data = sys.stdin.read().split()
n = int(data[0])
a = list(map(int, data[1 : 1 + n]))
m = int(data[1 + n])
b = list(map(int, data[2 + n : 2 + n + m]))
u, i, j = [], 0, 0
while i < n or j < m:
if j == m or (i < n and a[i] <= b[j]):
v = a[i]
i += 1
else:
v = b[j]
j += 1
if not u or u[-1] != v:
u.append(v)
print(*u)Java solution
import java.util.*;
public class Main {
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
long[] a = new long[n];
for (int i = 0; i < n; i++) a[i] = sc.nextLong();
int m = sc.nextInt();
long[] b = new long[m];
for (int i = 0; i < m; i++) b[i] = sc.nextLong();
List<Long> u = new ArrayList<>();
int i = 0, j = 0;
while (i < n || j < m) {
long v = (j == m || (i < n && a[i] <= b[j])) ? a[i++] : b[j++];
if (u.isEmpty() || u.get(u.size() - 1) != v) u.add(v);
}
StringBuilder sb = new StringBuilder();
for (int k = 0; k < u.size(); k++) sb.append(u.get(k)).append(k + 1 < u.size() ? " " : "");
System.out.println(sb);
}
}Solve Union of Two Sorted Arrays online · All practice problems