Remove Duplicates from an Integer Array - Java

Category: Medium | Concepts used: Set-based deduplication, order preservation

---

Problem Statement

Given an array of integers, return an array with all duplicate values removed (each value appears once).

Input : [1, 2, 2, 3, 4, 4, 5]      Output: [1, 2, 3, 4, 5]

Examples (with edge scenarios)

#	Input	Output	Why
1	[1, 2, 2, 3, 4, 4, 5]	[1, 2, 3, 4, 5]	Duplicates collapsed to single occurrence
2	[] (empty)	[]	Nothing to deduplicate
3	[7] (single element)	[7]	Trivially unchanged
4	[5, 5, 5]	[5]	All same value collapses to one
5	[3, 1, 2, 1, 3] (order matters)	[3, 1, 2]	First occurrence order should be preserved unless told otherwise

Common Fresher Mistake

Mistake	What happens	Fix
Sorting the array first, then deduplicating	Changes the original order — only acceptable if order doesn’t matter or sorted output is fine	Use LinkedHashSet to deduplicate while preserving first-seen order
Modifying the array size directly (Java arrays are fixed-length!)	Not directly possible — arrays can’t shrink in Java	Convert to a List or build a new array of the correct smaller size

---

Before You Code: Clarify the Contract

Before choosing an algorithm, confirm whether the array may be null or empty, whether duplicates and original order matter, whether the method may modify the input, and whether the answer should contain values or original indices. These choices can change both the code and the best data structure.

Analogy: The Assembly Line Scanner

Imagine you are a quality inspector monitoring products coming down a factory assembly line:

• You have a scanner (the LinkedHashSet) and a clean box (the output array).
• As each product passes by:
  • If the product’s barcode has never been seen before, you register the barcode and place the product in the clean box (uniqueValues.add(num)).
  • If the barcode has already been scanned, you discard the duplicate product immediately.
• The clean box ends up containing exactly one of each product, in the precise order they originally arrived down the assembly line!

---

Solution 1 — Using LinkedHashSet (Recommended, Preserves Order)

Intuition

A Set automatically discards duplicates the moment you try to add something already present — that’s its whole purpose. Using LinkedHashSet specifically also remembers the order things were first added, so simply dumping the array into one, in order, naturally gives us “each value once, in first-seen order” for free.

import java.util.LinkedHashSet;

public class RemoveDuplicates {
    public static int[] removeDuplicates(int[] arr) {
        LinkedHashSet<Integer> uniqueValues = new LinkedHashSet<>();
        for (int num : arr) {
            uniqueValues.add(num); // duplicates automatically ignored
        }

int[] result = new int[uniqueValues.size()];
        int index = 0;
        for (int num : uniqueValues) {
            result[index++] = num;
        }
        return result;
    }

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

int[] result2 = removeDuplicates(new int[]{3, 1, 2, 1, 3});
        System.out.println(java.util.Arrays.toString(result2)); // [3, 1, 2]
    }
}

Output:

[1, 2, 3, 4, 5]
[3, 1, 2]

Dry Run (arr = [3, 1, 2, 1, 3])

uniqueValues = {}
3 -> add -> {3}
1 -> add -> {3,1}
2 -> add -> {3,1,2}
1 -> already present -> ignored
3 -> already present -> ignored

Final set (insertion order): {3, 1, 2}
Converted to array: [3, 1, 2]

Interviewer’s take

This is the expected, clean solution — LinkedHashSet is purpose-built for exactly this “deduplicate while preserving order” requirement. It’s important to specify LinkedHashSet (not plain HashSet) if order preservation matters, which is a detail interviewers actively check for.

Follow-up questions you might get:

• “Why not use a plain HashSet?” → HashSet doesn’t guarantee any particular iteration order, so the output order could come out scrambled — LinkedHashSet fixes this while still giving O(1) average add/lookup.
• “What if order doesn’t matter and you also want the result sorted?” → Use a TreeSet instead — same deduplication behavior, but keeps everything in sorted order automatically.

---

Solution 2 — Sort First, Then Skip Adjacent Duplicates (If Order Doesn’t Matter)

Intuition

Once an array is sorted, all duplicate values become neighbors — so instead of checking the whole array for “have I seen this before,” we only need to compare each element to the one right before it. If it’s different from its predecessor, it’s a new unique value; if it matches, it’s a duplicate we can skip.

import java.util.Arrays;

public class RemoveDuplicatesSorted {
    public static int[] removeDuplicates(int[] arr) {
        int[] sorted = arr.clone();
        Arrays.sort(sorted);

int[] temp = new int[sorted.length];
        int count = 0;

for (int i = 0; i < sorted.length; i++) {
            if (i == 0 || sorted[i] != sorted[i - 1]) { // different from previous
                temp[count++] = sorted[i];
            }
        }
        return Arrays.copyOf(temp, count); // trim to the actual unique count
    }

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

Output:

[1, 2, 3, 4, 5]

Dry Run (arr = [3, 1, 2, 1, 3])

sorted = [1, 1, 2, 3, 3]
i=0: first element -> keep -> temp=[1]
i=1: sorted[1]=1 == sorted[0]=1 -> skip (duplicate)
i=2: sorted[2]=2 != sorted[1]=1 -> keep -> temp=[1,2]
i=3: sorted[3]=3 != sorted[2]=2 -> keep -> temp=[1,2,3]
i=4: sorted[4]=3 == sorted[3]=3 -> skip

Final: [1, 2, 3]  (note: original insertion order [3,1,2] is LOST here, output is sorted)

Interviewer’s take

This works well and is very efficient if the original order doesn’t need to be preserved (or a sorted result is actually preferred). It’s a classic pattern (sort, then compare adjacent elements) that’s reused in many array problems. Just be clear that this approach changes the order — only offer it if that’s acceptable, or the interviewer explicitly wants sorted output.

---

📊 Visual Flowchart

graph TD
    Start["Input Array arr"] --> Init["Initialize LinkedHashSet seen"]
    Init --> Loop{"i < arr.length?"}
    Loop -->|Yes| CheckSet{"seen.contains(arr[i])?"}
    CheckSet -->|No| Insert["seen.add(arr[i])"]
    CheckSet -->|Yes| Skip["Skip (Duplicate)"]
    Insert --> Next["i++"]
    Skip --> Next
    Next --> Loop
    Loop -->|No| Convert["Convert seen to int[] array"]
    Convert --> End["Return output array"]

---

Final Verdict — Which Solution Should You Give?

Order must be preserved?
        │
        ├── YES ──► Solution 1 (LinkedHashSet)
        │
        └── NO / sorted output is fine ──► Solution 2 (sort + skip adjacent)

• Both are considered “good” solutions — the right choice depends entirely on whether order preservation matters, which is worth clarifying with the interviewer up front.

---

Quick Recap

Approach	Time	Space	Preserves original order?
LinkedHashSet	O(n)	O(n)	Yes
Sort + skip adjacent duplicates	O(n log n)	O(n)	No (result is sorted)