How to Remove Duplicates from Unsorted Array in Java? [Solved]

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 sometime array is sorted and other times it's not-sorted or unsorted. Sometimes, 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, but 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 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 a  good data structure and algorithm course like Data Structures and Algorithms: Deep Dive Using Java on Udemy 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 array is that duplicate will come together, making it easy to remove them.

By the way, this solution will not work if 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 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 course to learn algorithms fundamentals in Java.

How to Remove Duplicates from Unsorted Array 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 into 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 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.

How to Remove Duplicates from Unsorted Array in Java


This is a good solution and also shows how the intelligent use of a data structure can make the solution easy. The code is very easy 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 interviewer still put another constraint and ask 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 has its pros and cons. The key thing is that you should start with the solution with the highest time and space complexity and then reach to the most efficient one. This is one of the technique I always use on interviews with bringing the interviewer to my strong areas.

Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Introduction to Algorithms
Cracking The Coding Interview
Data Structures and Algorithms Specialization - Coursera


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 integer array whose sum is equal to a given number? [solution]
  • Write a program to find top two numbers from an integer array? [solution]
  • 30+ Array-based Coding Problems from 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 find the largest and smallest number from a given array in Java? [solution]
  • 10 Free Data Structure and Algorithms Courses for Programmers [courses]
  • Write a program to find the missing number in 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 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 with your friends and colleagues. If you have any doubt 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.

No comments:

Post a Comment