Advertisement
Home Data Structure Arrays Merge Two Arrays without Duplicates

Merge Two Arrays without Duplicates

1
Advertisement

Title: Merge Two Arrays without Duplicates

In this guide, you will learn how to merge two arrays in Java while removing any duplicate values from the combined result. This comes up often in interviews when you are asked to combine two data sets, such as two lists of user IDs, without keeping repeated entries.

We will walk through a clean LinkedHashSet based approach, trace it on a sample input, and then look at examples, common mistakes, and edge cases so you can defend this solution confidently in an interview.

Understanding the Problem

Given two integer arrays, arr1 and arr2, the task is to produce a single array that contains every distinct value found in either array, with no value repeated. The two input arrays may overlap, be of different lengths, contain negative numbers, or even be empty.

The order of elements in the final merged array does not need to match a sorted sequence, but it helps readability if the result preserves the order in which values were first encountered across the two arrays.

Approach / Algorithm Steps

The simplest way to merge and deduplicate in one pass is to insert every value into a LinkedHashSet, which rejects duplicates automatically and remembers insertion order.

  1. Create an empty LinkedHashSet<Integer> called merged.
  2. Iterate over arr1 and add each value to merged.
  3. Iterate over arr2 and add each value to merged; the set silently ignores any value already present.
  4. Create a new int[] result array sized to merged.size().
  5. Copy the values out of merged into the result array in iteration order.
  6. Return the result array to the caller.

Java Program

Java
import java.util.LinkedHashSet;
import java.util.Set;

public class MergeArraysWithoutDuplicates {

    public static int[] mergeArrays(int[] arr1, int[] arr2) {
        Set<Integer> merged = new LinkedHashSet<>();

        for (int value : arr1) {
            merged.add(value);
        }

        for (int value : arr2) {
            merged.add(value);
        }

        int[] result = new int[merged.size()];
        int index = 0;
        for (int value : merged) {
            result[index] = value;
            index++;
        }

        return result;
    }

    public static void main(String[] args) {
        int[] arr1 = {1, 3, 5, 7, 9};
        int[] arr2 = {3, 5, 11, 13};

        int[] merged = mergeArrays(arr1, arr2);

        System.out.print("Merged array without duplicates: ");
        for (int value : merged) {
            System.out.print(value + " ");
        }
    }
}

Explanation of the Program

  • mergeArrays declares a LinkedHashSet<Integer> named merged. A HashSet would also deduplicate, but it does not guarantee any particular iteration order.
  • The first for loop adds every element of arr1 to merged. Since a set cannot hold duplicates, this step alone already removes repeats within arr1 itself.
  • The second for loop adds every element of arr2. Any value that already exists in merged is simply ignored by add, which is how cross-array duplicates get dropped.
  • A new int[] called result is allocated using merged.size(), which is exactly the count of distinct values, not arr1.length + arr2.length.
  • The final loop walks merged in insertion order and copies each value into result at the next free index.
  • main demonstrates the method on two overlapping arrays and prints the merged, duplicate-free result.

Step-by-Step Trace

Consider arr1 = [2, 4, 6] and arr2 = [4, 6, 8]. The table below shows the state of merged after each value is processed, in the order the algorithm visits them.

StepSourceValueAlready in merged?merged after this step
1arr1[0]2no{2}
2arr1[1]4no{2, 4}
3arr1[2]6no{2, 4, 6}
4arr2[0]4yes{2, 4, 6}
5arr2[1]6yes{2, 4, 6}
6arr2[2]8no{2, 4, 6, 8}

At the end of each step, merged holds exactly the distinct values seen so far, in the order they were first encountered.

Examples

Example 1: Arrays with Overlapping Values

When both arrays share several values, those shared values appear only once in the merged result.

Java
int[] arr1 = {10, 20, 30};
int[] arr2 = {20, 30, 40};
int[] merged = mergeArrays(arr1, arr2);
// merged = [10, 20, 30, 40]

Example 2: Merging with an Empty Array

If one array is empty, the merged result is simply the distinct values of the other array.

Java
int[] arr1 = {5, 6, 7};
int[] arr2 = {};
int[] merged = mergeArrays(arr1, arr2);
// merged = [5, 6, 7]

Example 3: Arrays with Negative Numbers

The approach works the same way regardless of sign, since LinkedHashSet compares values with equals, not magnitude.

Java
int[] arr1 = {-3, -1, 0};
int[] arr2 = {-1, 2, 0};
int[] merged = mergeArrays(arr1, arr2);
// merged = [-3, -1, 0, 2]

Common Mistakes to Avoid

These are the mistakes candidates most often make when solving this problem under interview conditions.

  • Checking duplicates with an ArrayList – calling list.contains(value) inside a loop over both arrays works but degrades to O(n * m) time. Use a Set so each lookup is O(1).
  • Using a plain HashSet when order matters – a HashSet deduplicates correctly but does not preserve the order values were inserted, so the merged array can come out in a surprising order. Use LinkedHashSet if the original order should be kept.
  • Sizing the result array with arr1.length + arr2.length – this overallocates whenever there are duplicates, leaving trailing zeros in the result. Size the array from merged.size() instead.
  • Mutating one of the input arrays in place – overwriting arr1 to build the merged result corrupts the caller’s data if they still need the original array. Always build a fresh result array.
  • Forgetting that autoboxing affects equality – comparing boxed Integer values with == instead of equals can misbehave outside the cached -128 to 127 range. Rely on Set.add, which already uses equals correctly, instead of hand-rolled comparisons.

Edge Cases to Test

Walk through these input shapes before calling the problem solved.

  • Both arrays empty
  • One array empty, the other non-empty
  • Arrays with no overlapping elements
  • Arrays that are identical
  • Arrays containing negative numbers
  • Single-element arrays
  • Duplicate values repeated within the same array
  • Integer.MIN_VALUE / Integer.MAX_VALUE present

Additional Considerations

The algorithm runs in O(n + m) time, where n and m are the lengths of arr1 and arr2, since every element is inserted into the set once and the set offers O(1) average-case add and lookup.

Space complexity is also O(n + m) in the worst case, when none of the values overlap and the set has to hold every element from both arrays plus the final result array.

Autoboxing int values into Integer objects for the set does add some overhead compared to a pure primitive-array approach. If both arrays are already sorted, a two-pointer merge avoids boxing entirely and is worth preferring in that scenario.

Interview Follow-up Questions

An interviewer will often extend this problem to see how your approach adapts to new constraints.

  • What if both arrays are already sorted? – use a two-pointer merge that skips a value when it equals the last value written to the result, avoiding the set entirely.
  • What if you need the merged array sorted instead of in first-seen order? – swap the LinkedHashSet for a TreeSet, trading O(log n) inserts for automatic ordering.
  • What if duplicates need to be counted rather than discarded? – use a HashMap<Integer, Integer> to tally occurrences of each value across both arrays instead of a Set.
  • What if the arrays are too large to hold in memory at once? – stream each array from disk in sorted chunks and dedup during an external merge, so only a small window of values is held in memory at any time.
  • What if you must solve this with no extra Set or Map at all? – sort both arrays in place, then merge and dedup with two pointers, giving O((n + m) log(n + m)) time but only O(1) extra space beyond the output.

Conclusion

Merging two arrays without duplicates is a great example of picking the right data structure for the job. A LinkedHashSet gives you deduplication and predictable ordering in a single pass, which is usually all an interviewer is looking for.

Try adapting the code above to merge three or more arrays, or to work with String values instead of int. You can learn more about Arrays: https://dailyjavaconcept.com/category/data-structure/arrays/