easyArray ProblemsJava

Remove Duplicates From an Unsorted Array

Remove duplicates from an unsorted array while preserving first-occurrence order.

Quick Answer

Walk the array and keep a set of values you have already seen. For each element, if it is not in the set, add it to both the set and the result; if it is already there, skip it. Using a LinkedHashSet preserves the order of first appearance while giving O(n) overall time.

Problem Statement

Given an unsorted array, remove the duplicate values so each distinct element appears once. Unlike the sorted version, equal values are not adjacent, so you cannot rely on comparing neighbours.

Keep the first occurrence of each value and preserve that order in the output. Return the array (or list) of unique elements.

Input: An unsorted array arr of length n.

Output: The unique elements in order of first appearance.

Examples

Example 1
Input:  [4, 5, 4, 6, 5, 7]
Output: [4, 5, 6, 7]

The second 4 and second 5 are skipped; first-seen order 4, 5, 6, 7 is kept.

Example 2
Input:  [1, 1, 1, 2, 3, 3]
Output: [1, 2, 3]

Only the first 1 and first 3 survive, giving 1, 2, 3.

Constraints

  • 0 <= n <= 10^6
  • Order of first occurrence must be preserved

Think Before You Code

Reveal the questions to ask yourself first
  • How do you know whether you have seen a value before without re-scanning?
  • Which data structure gives fast membership checks?
  • How do you keep the output in first-seen order?

Hints

Open them one at a time — try after each before revealing the next.

Hint 1
You need a fast way to remember which values already appeared.
Hint 2
A hash set answers 'have I seen this?' in O(1) on average.
Hint 3
A `LinkedHashSet` both deduplicates and preserves insertion order — add every element and it keeps only firsts, in order.

Approach

Reveal the step-by-step approach

Track seen values and keep only the first occurrence of each.

  1. Create a LinkedHashSet<Integer> (it ignores duplicate adds and preserves order).
  2. For each element x in the array, add it to the set.
  3. The set now holds the unique values in first-seen order — copy them into a result array.

The set membership check is what turns an otherwise O(n^2) scan into an average O(n) solution, at the cost of O(n) extra space for the set.

Dry Run

Walk through the example step by step

Deduplicating [4, 5, 4, 6, 5, 7]:

element | in set already? | action        | set contents
--------+-----------------+---------------+----------------
4       | no              | add 4         | {4}
5       | no              | add 5         | {4, 5}
4       | yes             | skip          | {4, 5}
6       | no              | add 6         | {4, 5, 6}
5       | yes             | skip          | {4, 5, 6}
7       | no              | add 7         | {4, 5, 6, 7}
------------------------------------ result [4, 5, 6, 7]

Solution

Reveal the full Java solution
import java.util.Arrays;
import java.util.LinkedHashSet;
import java.util.Set;

public class RemoveDuplicatesUnsorted {
    public static int[] removeDuplicates(int[] arr) {
        Set<Integer> seen = new LinkedHashSet<>();
        for (int x : arr) {
            seen.add(x);
        }
        int[] result = new int[seen.size()];
        int i = 0;
        for (int x : seen) {
            result[i++] = x;
        }
        return result;
    }

    public static void main(String[] args) {
        System.out.println(Arrays.toString(removeDuplicates(new int[]{4, 5, 4, 6, 5, 7}))); // [4, 5, 6, 7]
        System.out.println(Arrays.toString(removeDuplicates(new int[]{1, 1, 1, 2, 3, 3}))); // [1, 2, 3]
    }
}

A LinkedHashSet rejects duplicate insertions while remembering the order values were first added, so a single pass of add calls leaves exactly the unique elements in first-seen order. Copying the set into an array gives the result. The set costs O(n) extra space, which is the price of handling data that is not sorted.

Time: O(n) averageSpace: O(n)

Common Mistakes

  • Using a plain `HashSet`, which deduplicates but loses the first-seen order.
  • Comparing only adjacent elements as if the array were sorted, missing far-apart duplicates.
  • Nesting two loops to compare every pair, which is O(n^2) and slow on large inputs.

Edge Cases to Test

  • Empty array [] returns an empty array.
  • All elements identical, e.g. [7, 7, 7], returns [7].
  • Already-unique array is returned unchanged in the same order.

Interview Follow-Ups

  • How would you remove duplicates in place if O(1) extra space were required?
  • How would you keep the last occurrence instead of the first?
  • How would the approach change for a sorted array?

Practising for Java interviews?

CodeBegun's Java Full Stack with AI program builds this problem-solving muscle with mentor review and mock interviews.

Explore the Java Full Stack program →
Chat with us