Union of Two Sorted Arrays — Solution in Python, Java & C++
Union of Two Sorted Arrays solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. An easy problem.
Union of Two Sorted Arrays is an easy coding problem on arrays and two pointers, asked in TCS, Infosys and Capgemini interviews.
- Difficulty: Easy
- Topics: Arrays, Two Pointers
- Asked at: TCS, Infosys, Capgemini
- Time limit: 2 s
- Memory limit: 256 MB
- Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby
Problem statement
Given two arrays a and b sorted in non-decreasing order, return their union: every distinct value that appears in either array, listed in increasing order.
Each array may contain duplicates; the result must not.
Example 1
Input: a = [1,2,3,4,5], b = [1,2,3]
Output: [1,2,3,4,5]
Example 2
Input: a = [2,2,3,4,5], b = [1,1,2,3,4]
Output: [1,2,3,4,5]
Example 3
Input: a = [1,1,1], b = [1]
Output: [1]
Constraints
1 <= a.length, b.length <= 100000-1000000000 <= a[i], b[i] <= 1000000000Both arrays are sorted non-decreasing.
Hints for Union of Two Sorted Arrays
Hint 1
Both inputs are already sorted — a merge does the job without any extra sorting.
Hint 2
Advance the pointer at the smaller value; when they tie, advance both.
Hint 3
Suppress duplicates by comparing against the last value you appended.
How to solve Union of Two Sorted Arrays
This is one merge step of merge sort with duplicate suppression: because both inputs are sorted, the union comes out in order for free.
Approach
- Walk two pointers
iandj. - Append the smaller of
a[i]andb[j]and advance that pointer; on a tie, append once and advance both. - Before every append, skip the value if it equals the last one already in the output.
- Drain whichever array still has elements, applying the same duplicate check.
Why it works
Values are emitted in non-decreasing order, so any duplicate must be adjacent in the output — comparing against the last appended value is therefore enough to make the result distinct.
Complexity
- Time —
O(n + m) - Space —
O(n + m) for the output
Pitfalls
- Concatenating and sorting is O((n+m) log(n+m)) and throws away the sortedness you were given.
- On a tie you must advance both pointers, or the shared value is emitted from the other array on the next step.
- The drain loops need the same duplicate guard — the tail of one array can repeat the last merged value.
Reference solution
Python
from typing import List
def findUnion(a: List[int], b: List[int]) -> List[int]:
out = []
i = 0
j = 0
def push(v):
if not out or out[-1] != v:
out.append(v)
while i < len(a) and j < len(b):
if a[i] < b[j]:
push(a[i])
i += 1
elif b[j] < a[i]:
push(b[j])
j += 1
else:
push(a[i])
i += 1
j += 1
while i < len(a):
push(a[i])
i += 1
while j < len(b):
push(b[j])
j += 1
return outJava
public static int[] findUnion(int[] a, int[] b) {
int[] tmp = new int[a.length + b.length];
int m = 0, i = 0, j = 0;
while (i < a.length && j < b.length) {
int v;
if (a[i] < b[j]) v = a[i++];
else if (b[j] < a[i]) v = b[j++];
else { v = a[i]; i++; j++; }
if (m == 0 || tmp[m - 1] != v) tmp[m++] = v;
}
while (i < a.length) {
int v = a[i++];
if (m == 0 || tmp[m - 1] != v) tmp[m++] = v;
}
while (j < b.length) {
int v = b[j++];
if (m == 0 || tmp[m - 1] != v) tmp[m++] = v;
}
int[] out = new int[m];
for (int k = 0; k < m; k++) out[k] = tmp[k];
return out;
}C++
vector<int> findUnion(vector<int>& a, vector<int>& b) {
vector<int> out;
size_t i = 0, j = 0;
auto push = [&](int v) {
if (out.empty() || out.back() != v) out.push_back(v);
};
while (i < a.size() && j < b.size()) {
if (a[i] < b[j]) push(a[i++]);
else if (b[j] < a[i]) push(b[j++]);
else { push(a[i]); i++; j++; }
}
while (i < a.size()) push(a[i++]);
while (j < b.size()) push(b[j++]);
return out;
}JavaScript
var findUnion = function(a, b) {
const out = [];
function push(v) {
if (out.length === 0 || out[out.length - 1] !== v) out.push(v);
}
let i = 0, j = 0;
while (i < a.length && j < b.length) {
if (a[i] < b[j]) { push(a[i]); i++; }
else if (b[j] < a[i]) { push(b[j]); j++; }
else { push(a[i]); i++; j++; }
}
while (i < a.length) { push(a[i]); i++; }
while (j < b.length) { push(b[j]); j++; }
return out;
};Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.
All 1199 arrays problems · the whole catalogue
Learn the technique: Arrays · Two Pointers Technique