[Solved] How to remove duplicate elements from Array in Java? Example

This is one of the common technical interview questions which are asked to entry-level programmers and software engineers. There are also a lot of variants of how do you remove duplicates from an array in Java, like sometimes the array is sorted, and other times it's not sorted or unsorted. Sometimes, the Interviewer just spends more than half of the interview on this question by progressively making it more difficult by imposing new constraints like removing duplicate elements in place or without using any additional data structure, etc.

Btw, If you are allowed to use Java's Collection framework, then this is quite easy to solve. Still, if you are not allowed to use Set, Iterator, and other Java utility classes, then it suddenly becomes a tricky algorithm question. 

Anyway, before talking about solutions, let's first understand the problem. You have given an unsorted array of integers, and you have to remove all duplicates from it.

 For example if input array is {22, 3, 22, 11, 24, 24, 4, 3} then output array should be {22, 3, 11, 24, 4} i.e. duplicate elements 22, 24 and 3 must be removed from original array. by the way, maintaining the original order of elements is not necessary, this is something you can ask your Interviewer.

I am sure at first he will allow you to solve it without bothering about the original order, but depending on how you do, he may ask you do it again, but this time keeping the original order intact. Let's see different approaches to solve this problem.

Btw, if you are not familiar with the array data structure and essential data structures like a hash table, set, binary tree, etc. then it's better to first go through these best data structure and algorithm courses to learn more about basic data structure and Programming techniques in Java.

How to Remove Duplicates from unsorted Array in Java

The first and easiest approach to remove duplicates is to sort the array using QuickSort or MergeSort in O(nlogn) time and then remove repeated elements in O(n) time. One advantage of sorting arrays is that duplicates will come together, making it easy to remove them.

By the way, this solution will not work if the Interviewer will put constraints like you cannot sort the array or original order of elements must be preserved in the output array. In that case, we need to

Another way to remove duplicates from an integer array is to use a binary tree. You can construct a binary search tree using numbers from an array and discard all numbers, which are duplicates. The binary tree will only contain non-repeated values, which you can later convert it an array.

However, the drawback of this solution is that the original order of the element is not preserved. The time complexity of this solution is O(nLogn) because inserting a node in the binary tree will take O(LogN) time, and we need to add n nodes, where n is the size of the array.

If you have trouble calculating the time and space complexity of your algorithms or want to know more about Big(O) notation, then you can also check out Algorithms and Data Structures - Part 1 and 2  courses on Pluralsight. These two are some of the best courses to learn algorithms fundamentals in Java.

Java Program to Remove Duplicates from Unsorted Array

Now let's see a pure Java solution, where you are allowed to use the Set interface. You solve this problem by using HashSet or LinkedHashSet. If you are asked to preserve the order of elements, then you can use LinkedHashSet, as it maintains the order on which elements are added to it.

package tool;

import static org.junit.Assert.assertArrayEquals;

import java.util.HashSet;
import java.util.Set;

import org.junit.Test;

public class DuplicateArray {

  private Integer[] removeDuplicates(Integer[] input) {
    if (input == null || input.length <= 0) {
      return input;
    }

    Set<Integer> aSet = new HashSet<>(input.length);

    // set will reject all duplicates
    for (int i : input) {
      aSet.add(i);
    }

    return aSet.toArray(new Integer[aSet.size()]);
  }

  @Test
  public void testArrayWithDuplicates() {
    Integer[] given = new Integer[] { 1, 2, 3, 3 };
    Integer[] actual = removeDuplicates(given);
    Integer[] expected = new Integer[] { 1, 2, 3 };
    assertArrayEquals(expected, actual);
  }

  @Test
  public void testArrayWithoutDuplicates() {
    Integer[] given = new Integer[] { 1, 2, 3 };
    Integer[] actual = removeDuplicates(given);
    Integer[] expected = new Integer[] { 1, 2, 3 };
    assertArrayEquals(expected, actual);
  }

  @Test
  public void testWithEmptyArray() {
    Integer[] given = new Integer[] {};
    Integer[] actual = removeDuplicates(given);
    Integer[] expected = new Integer[] {};
    assertArrayEquals(expected, actual);
  }

  @Test
  public void testWithNull() {
    Integer[] given = null;
    Integer[] actual = removeDuplicates(given);
    Integer[] expected = null;
    assertArrayEquals(expected, actual);
  }

  @Test
  public void testArrayWithAllDuplicates() {
    Integer[] given = new Integer[] { 3, 3, 3 };
    Integer[] actual = removeDuplicates(given);
    Integer[] expected = new Integer[] { 3 };
    assertArrayEquals(expected, actual);
  }

  @Test
  public void testArrayWithMultipleDuplicates() {
    Integer[] given = new Integer[] { 1, 2, 3, 3, 4, 4, 5, 5, 5 };
    Integer[] actual = removeDuplicates(given);
    Integer[] expected = new Integer[] { 1, 2, 3, 4, 5 };
    assertArrayEquals(expected, actual);
  }

}

And when you run this program as a JUnit test in Eclipse, you will see a green bar like below, which indicates that all test cases are passed, and our solution is working fine.

This is a good solution and also shows how the intelligent use of a data structure can make the solution easy. The code is straightforward to read and understand, and it's also very efficient in terms of CPU time as you just need O(n) time to solve this problem.

Btw, if the Interviewer still puts another constraint and asks you to remove duplicates without using Java Collection API, then you have no choice but to iterate over an array and compare each and every element to find and remove duplicates.  The full solution is discussed here, which you can also see after you have tried.


That's all about how to remove duplicates from an unsorted array in Java. Every solution is acceptable, but all have their pros and cons. The critical thing is that you should start with the solution with the highest time and space complexity and then reach the most efficient one. This is one of the techniques I always use in interviews with bringing the Interviewer to my strong areas.


Other Array Coding Problems to Practice
If you are interested in solving more Array-based algorithm problems, then here is the list of some of the frequently asked coding problems from interviews:

• How to find all pairs on an integer array whose sum is equal to a given number? [solution]
• Write a program to find the top two numbers from an integer array? [solution]
• 30+ Array-based Coding Problems from Interviews (questions)
• 100+ Coding Problems to Crack Programming Interviews (questions)
• How to check if an array contains a number in Java? [solution]
• How do you remove duplicates from an array in place? [solution]
• How to solve the two-sum problems in Java? [solution)
• How to find the largest and smallest number from a given array in Java? [solution]
• Book Review - Grokking Algorithms (review)
• 10 Free Data Structure and Algorithms Courses for Programmers [courses]
• Write a program to find the missing number in an integer array of 1 to 100? [solution]
• How do you reverse an array in place in Java? [solution]
• How to find the maximum and minimum number in an unsorted array? [solution]
• 10 Algorithms courses to Crack Coding Interviews [courses]
• How to sort an array in place using the QuickSort algorithm? [solution]
• How do you print all duplicate elements from the array in Java? [solution]
• 50+ Data Structure and Algorithms Coding Problems from Interviews (questions)
• 10 Algorithms Books Every Programmer should read [books]

Thanks for reading this article. If you like this interview question, then please share it with your friends and colleagues. If you have any doubts or feedback, then please drop a note.


P. S. - If you are looking for some Free Algorithms courses to improve your understanding of Data Structure and Algorithms, then you should also check this list of Free Data Structure and Algorithms Courses for Programmers.