Union of Two Sorted Arrays with Distinct Elements

JavaView on GFG

Time: O(n+m)

Space: O(n+m)

Intuition

Merge two sorted arrays keeping only distinct elements. Two-pointer merge.

Algorithm

1Two pointers. Pick smaller element. Skip duplicates. O(m+n).

Common Pitfalls

•Merge step of merge sort, but skip duplicates. Check both arrays and result for duplicates.

Union of Two Sorted Arrays with Distinct Elements.java

Java

// Approach: Two pointer merge: collect all distinct elements from both sorted arrays.
// Time: O(n+m) Space: O(n+m)
class Solution {
    // Function to return a list containing the union of the two arrays.
    public static ArrayList<Integer> findUnion(int a[], int b[]) {
        HashSet<Integer> set = new HashSet<>();
        ArrayList<Integer> union = new ArrayList<>();

        for (int i : a)
            set.add(i);

        for (int j : b) {
            if (!set.contains(j))
                set.add(j);
        }
        for (int k : set)
            union.add(k);

        Collections.sort(union);
        return union;
    }
}

Was this solution helpful?