Getting everything ready for you…

Loading courses, problems and your progress. This takes just a moment.

0s

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

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

  1. Walk both arrays with one pointer each, always taking the smaller current value.
  2. 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