Union of Two Sorted Arrays

Easy
507.

Union of Two Sorted Arrays

Union of Two Sorted Arrays is an easy coding problem on arrays and two pointers, asked in TCS, Infosys and Capgemini interviews.

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] <= 1000000000
  • Both arrays are sorted non-decreasing.
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[]} a
 * @param {number[]} b
 * @return {number[]}
 */
var findUnion = function(a, b) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

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] <= 1000000000
  • Both arrays are sorted non-decreasing.

Hints for Union of Two Sorted Arrays

  1. Hint 1

    Both inputs are already sorted — a merge does the job without any extra sorting.

  2. Hint 2

    Advance the pointer at the smaller value; when they tie, advance both.

  3. 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

  1. Walk two pointers i and j.
  2. Append the smaller of a[i] and b[j] and advance that pointer; on a tie, append once and advance both.
  3. Before every append, skip the value if it equals the last one already in the output.
  4. 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 out

Java

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