Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

Union of Two Arrays

Try it yourself
EasyProblemExternal link

Description

You are given two arrays a[] and b[], each sorted in increasing order. Either array may contain the same value more than once.

Return their union: every distinct value that appears in a or in b, each exactly once, in increasing order.

Examples

Example 1

Input: a = [1, 3, 3, 5, 8], b = [2, 3, 5, 5, 9]

Output: [1, 2, 3, 5, 8, 9]

Explanation: 3 appears in both arrays and twice in a, and 5 appears in both and twice in b; each is kept once. 1 and 8 come only from a, and 2 and 9 only from b.

Example 2

Input: a = [-4, -4, 0], b = [-4, 2]

Output: [-4, 0, 2]

Explanation: Negative values follow the same rule. -4 appears three times across the two arrays and is kept once.

Example 3

Input: a = [7, 7, 7], b = [7]

Output: [7]

Explanation: Every value in both arrays is 7, so the union has a single value.

Constraints

  • 1 ≤ a.size(), b.size() ≤ 10^5
  • -10^9 ≤ a[i], b[i] ≤ 10^9
  • Both arrays are sorted in increasing order.

Editorial

Brute Force

Intuition

What the union is. Take every value that appears anywhere in the two arrays, keep each one once, and list them from smallest to largest. Repeats disappear whether they are inside one array or spread across both.

The arrays a = 1, 3, 3, 5, 8 and b = 2, 3, 5, 5, 9 with each value's first appearance kept and every repeat struck out, above their union, 1, 2, 3, 5, 8, 9: six distinct values out of ten, in increasing order.

The direct way. Go through a and then b. For each value, look through the answer built so far; if the value is not there, append it. Values are appended in the order they are first met, which is not sorted in general (in Example 1 it is 1, 3, 5, 8, 2, 9), so sort the answer at the end.

Looking a value up means reading the answer from its start: to the end when the value is new, and up to where it sits when it is a repeat.

Step-by-Step Explanation

We trace Example 1. The top row is a followed by b; the second row is the answer built so far. The value being handled is blue, and handled values stay green when they were new and orange when they were repeats.

Step 1: Read a and then b, value by value. The answer starts empty.

Step 2: 1: not in the answer (0 checked), append it.

Step 3: 3: not in the answer (1 checked), append it.

Step 4: 3: already in the answer, skip it.

Step 5: 5: not in the answer (2 checked), append it.

Step 6: 8: not in the answer (3 checked), append it.

Step 7: 2: not in the answer (4 checked), append it.

Step 8: 3: already in the answer, skip it.

Step 9: 5: already in the answer, skip it.

Step 10: 5: already in the answer, skip it.

Step 11: 9: not in the answer (5 checked), append it.

Step 12: The answer is 1, 3, 5, 8, 2, 9; sorted, 1, 2, 3, 5, 8, 9.

Brute Force — Scan the Answer for Every Value — Example 1: a followed by b. Each value is searched for in the answer built so far (second row); new values turn green, repeats orange.

Algorithm

  1. Let union be an empty list.
  2. For each value x of a, then of b: if x is not in union, append it.
  3. Sort union and return it.

Code

#include <algorithm>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> findUnion(vector<int>& a, vector<int>& b) {
        vector<int> all(a);
        all.insert(all.end(), b.begin(), b.end());
        vector<int> uni;
        for (int x : all)
            if (find(uni.begin(), uni.end(), x) == uni.end())  // a scan of the answer so far, to the end whenever x is new
                uni.push_back(x);
        sort(uni.begin(), uni.end());
        return uni;
    }
};
class Solution:
    def findUnion(self, a, b):
        union = []
        for x in a + b:
            if x not in union:  # a scan of the answer so far, to the end whenever x is new
                union.append(x)
        union.sort()
        return union
import java.util.ArrayList;
import java.util.Collections;

class Solution {
    public static ArrayList<Integer> findUnion(int a[], int b[]) {
        ArrayList<Integer> union = new ArrayList<>();
        for (int[] arr : new int[][] {a, b})
            for (int x : arr)
                if (!union.contains(x)) union.add(x);  // a scan of the answer so far, to the end whenever x is new
        Collections.sort(union);
        return union;
    }
}

Complexity Analysis

Let n and m be the lengths of a and b, and u the number of distinct values.

Time Complexity: O((n + m) · u). Each of the n + m values can scan the whole answer, which grows to u values. In the worst case, when almost every value is distinct, u is close to n + m and this is O((n + m)²). The sort at the end adds O(u log u).

Space Complexity: O(u) for the answer.

Why This Approach Is Not Efficient

The scan of the answer grows as the answer grows. Measured in Python with mostly distinct values, 2,000 + 2,000 values take 0.044 s, 4,000 + 4,000 take 0.15 s, 8,000 + 8,000 take 0.61 s and 16,000 + 16,000 take 2.5 s, four times longer each time the input doubles. At the full 10^5 + 10^5 that would be about 100 seconds.

What is needed is a way to answer "have I seen this value?" without reading everything seen so far.

Better Approach - A Hash Set, Then Sort

Intuition

A hash set remembers what it has seen. Put every value of both arrays into a hash set. A set keeps a single copy of each value, and checking or adding a value takes one step on average, however many values it already holds. So all the repeats disappear in one pass over the input.

Then sort. A hash set keeps no useful order, so copy its values into a list and sort it before returning.

In Python this whole approach is the one line sorted(set(a) | set(b)); | is set union. Measured, it takes 0.025 s for 10^5 + 10^5 values, the same as the code below.

Step-by-Step Explanation

We trace Example 1 again. The top row is a followed by b; the table is the hash set, and the line under it shows whether the current value was already there.

Step 1: Read a and then b; the set starts empty.

Step 2: 1: added, 1 in the set.

Step 3: 3: added, 2 in the set.

Step 4: 3: already in the set.

Step 5: 5: added, 3 in the set.

Step 6: 8: added, 4 in the set.

Step 7: 2: added, 5 in the set.

Step 8: 3: already in the set.

Step 9: 5: already in the set.

Step 10: 5: already in the set.

Step 11: 9: added, 6 in the set.

Step 12: Sort the 6 values in the set: 1, 2, 3, 5, 8, 9.

A Hash Set, Then One Sort — Example 1: every value of a and then b goes into a hash set, which ignores repeats; the set is sorted at the end.

Algorithm

  1. Put every value of a and of b into a hash set.
  2. Copy the set's values into a list, sort it, and return it.

Code

#include <algorithm>
#include <unordered_set>
#include <vector>
using namespace std;

class Solution {
public:
    vector<int> findUnion(vector<int>& a, vector<int>& b) {
        unordered_set<int> seen(a.begin(), a.end());  // keeps one copy of each value
        seen.insert(b.begin(), b.end());
        vector<int> uni(seen.begin(), seen.end());
        sort(uni.begin(), uni.end());  // a hash set has no order, so the answer is sorted at the end
        return uni;
    }
};
class Solution:
    def findUnion(self, a, b):
        seen = set()  # keeps one copy of each value, and says in one step whether a value is already in it
        for x in a + b:
            seen.add(x)
        return sorted(seen)  # a set has no order, so the answer is sorted at the end
import java.util.ArrayList;
import java.util.Collections;
import java.util.HashSet;

class Solution {
    public static ArrayList<Integer> findUnion(int a[], int b[]) {
        HashSet<Integer> seen = new HashSet<>();  // keeps one copy of each value
        for (int x : a) seen.add(x);
        for (int x : b) seen.add(x);
        ArrayList<Integer> union = new ArrayList<>(seen);
        Collections.sort(union);  // a hash set has no order, so the answer is sorted at the end
        return union;
    }
}

Complexity Analysis

Time Complexity: O(n + m + u log u). One pass fills the set; sorting its u values costs u log u.

Space Complexity: O(u) for the set and the list.

Why This Approach Is Not Efficient

This approach never uses the one thing the question promises: both arrays are already sorted. It throws that order away by putting the values in a hash set, and then pays to sort them all over again. It also needs a whole set's worth of extra memory.

In C++ the cost is clear: for 10^6 + 10^6 values the set-and-sort takes 0.42 s, while the next approach takes 0.005 s. In Python the gap is smaller, 0.43 s against 0.26 s, because the set and the sort run as compiled code there while the next approach's loop runs line by line.

Optimal Approach - Two Pointers Over the Sorted Arrays

Intuition

Merge the two sorted arrays, and skip repeats as you write. Keep one finger i on a and one finger j on b, both at the start. Compare the two front values and take the smaller one; on a tie, take the one from a. Because both arrays are sorted, the value taken is always the smallest value not yet taken, so the values come out in increasing order, as in the merge step of merge sort.

Midway through Example 1: the fingers rest on a[3] = 5 and b[2] = 5 and the union so far is 1, 2, 3. a's 5 is new and is written; b's two 5s then equal the last value written and are skipped.

Why comparing with the last value written is enough. Since the values come out in increasing order, all the copies of a value come out one right after another, from either array. So a value is a repeat exactly when it equals the value written just before it. No set is needed, and no sort.

When one array runs out, keep taking from the other one, still skipping values equal to the last one written.

In Java, compare numbers, not boxes. The answer is an ArrayList<Integer>, whose elements are objects. The code compares union.get(union.size() - 1) with an int, which compares the numbers. Comparing two Integer objects with != compares the objects instead. On a real run, two Integer objects both holding 100 compare as equal, because Java reuses the objects for -128 to 127, but two holding 1000 compare as different. So use .equals, or compare against an int as the code does.

Step-by-Step Explanation

We trace Example 1 one last time. Row 0 is a, row 1 is b and row 2 is the union being written. The two fronts are lit up in indigo; a value taken is green when it is written and orange when it is skipped as a repeat.

Step 1: Row 0 is a, row 1 is b, row 2 is the union. Both fingers start at the front.

Step 2: Take 1 from a: new, write it → 1.

Step 3: Take 2 from b: new, write it → 1, 2.

Step 4: Take 3 from a: new, write it → 1, 2, 3.

Step 5: Take 3 from a: equals the last value written, skip it.

Step 6: Take 3 from b: equals the last value written, skip it.

Step 7: Take 5 from a: new, write it → 1, 2, 3, 5.

Step 8: Take 5 from b: equals the last value written, skip it.

Step 9: Take 5 from b: equals the last value written, skip it.

Step 10: Take 8 from a: new, write it → 1, 2, 3, 5, 8.

Step 11: Take 9 from b: new, write it → 1, 2, 3, 5, 8, 9.

Step 12: Both arrays are done: 1, 2, 3, 5, 8, 9, with each value read once.

Two Pointers: Merge and Skip Repeats — Example 1. Row 0 is a, row 1 is b, row 2 is the union. The two fronts are compared, the smaller is written unless it repeats the last value.

Algorithm

  1. Let union be an empty list, and i = j = 0.
  2. While i < n or j < m:
    • If b is used up, or a is not and a[i] ≤ b[j]: take x = a[i] and add 1 to i. Otherwise take x = b[j] and add 1 to j.
    • If union is empty or its last value is not x, append x.
  3. Return union.

The tie goes to either side. When a[i] == b[j], taking either one is fine: the other becomes a repeat of the value just written and is skipped.

Code

#include <vector>
using namespace std;

class Solution {
public:
    vector<int> findUnion(vector<int>& a, vector<int>& b) {
        vector<int> uni;
        size_t i = 0, j = 0;
        while (i < a.size() || j < b.size()) {
            // take the smaller front value; once one array runs out, keep taking from the other
            int x = (j == b.size() || (i < a.size() && a[i] <= b[j])) ? a[i++] : b[j++];
            if (uni.empty() || uni.back() != x) uni.push_back(x);  // equal values come out next to each other
        }
        return uni;
    }
};
class Solution:
    def findUnion(self, a, b):
        union = []
        i = j = 0
        while i < len(a) or j < len(b):
            # take the smaller front value; once one array runs out, keep taking from the other
            if j == len(b) or (i < len(a) and a[i] <= b[j]):
                x = a[i]
                i += 1
            else:
                x = b[j]
                j += 1
            if not union or union[-1] != x:  # equal values come out next to each other, so this drops every repeat
                union.append(x)
        return union
import java.util.ArrayList;

class Solution {
    public static ArrayList<Integer> findUnion(int a[], int b[]) {
        ArrayList<Integer> union = new ArrayList<>();
        int i = 0, j = 0;
        while (i < a.length || j < b.length) {
            // take the smaller front value; once one array runs out, keep taking from the other
            int x = (j == b.length || (i < a.length && a[i] <= b[j])) ? a[i++] : b[j++];
            if (union.isEmpty() || union.get(union.size() - 1) != x) union.add(x);  // equal values come out next to each other
        }
        return union;
    }
}

Complexity Analysis

Time Complexity: O(n + m). Every value of both arrays is read exactly once. Measured in C++, 0.005 s for 10^6 + 10^6 values and 0.057 s for 10^7 + 10^7.

Space Complexity: O(1) apart from the answer itself, which needs O(u). This matches GfG's expected O(n + m) time and O(1) extra space.