How To Take Away Duplicates From Unsorted Array Inwards Java? [Solved]

This is ane of the mutual technical interview questions which are asked to entry-level programmers together with software engineers. There are also a lot of variants of how create you lot withdraw duplicates from an array inwards Java similar sometime array is sorted together with other times it's not-sorted or unsorted. Sometimes, Interviewer only spends to a greater extent than than one-half of the interview on this inquiry yesteryear progressively making it to a greater extent than hard yesteryear imposing novel constraints similar removing duplicate elements inwards house or without using whatsoever additional information structure, etc. Btw, If you lot are allowed to role Java's Collection framework hence this is quite tardily to solve, but if you lot are non allowed to role Set, Iterator, together with other Java utility classes hence it all of a abrupt becomes a tricky algorithm question.

Anyway, earlier talking well-nigh solutions, let's offset sympathise the problem. You direct hold given an unsorted array of integers together with you lot direct hold to withdraw all duplicates from it.

 For representative if input array is {22, 3, 22, 11, 24, 24, 4, 3} hence output array should endure {22, 3, 11, 24, 4} i.e. duplicate elements 22, 24 together with iii must endure removed from master array. yesteryear the way, maintaining the master companionship of elements is non necessary, this is something you lot tin displace inquire your Interviewer.

I am certain at offset he volition allow you lot to solve it without bothering well-nigh master order, but depending on how you lot do, he may inquire you lot create it in ane trial again but this fourth dimension keeping the master companionship intact. Let's come across dissimilar approaches to solve this problem.

Btw, if you lot are non familiar amongst the array information construction together with essential information structures similar a hash table, set, binary tree, etc hence it's improve to offset popular off through a  skillful information construction together with algorithm course of report like Data Structures together with Algorithms: Deep Dive Using Java on Udemy to larn to a greater extent than well-nigh basic information construction together with Programming techniques inwards Java.

How to Remove Duplicates from Unsorted Array inwards Java

The offset together with easiest approach to withdraw duplicates is to form the array using QuickSort or MergeSort inwards O(NLogN) time together with hence withdraw repeated elements inwards O(n) time. One wages of sorting array is that duplicate volition come upwards together, making it tardily to withdraw them.

By the way, this solution volition non operate if Interviewer volition seat constraints similar you lot cannot form the array or master companionship of elements must endure preserved inwards the output array. In that case, nosotros demand to

Another means to withdraw duplicates from an integer array is to role a binary tree. You tin displace build a binary search tree using numbers from an array together with discard all numbers which are duplicates. The binary tree volition alone comprise non repeated values, which you lot tin displace afterwards convert it an array.

However, the drawback of this solution is that the master companionship of the chemical cistron is non preserved. The fourth dimension complexity of this solution is O(nLogn) because inserting a node inwards the binary tree volition select O(LogN) fourth dimension together with nosotros demand to add together n nodes, where n is the size of the array.

If you lot direct hold problem calculating fourth dimension together with infinite complexity of your algorithms or desire to know to a greater extent than well-nigh Big(O) notation hence you lot tin displace also banking concern fit out HashSet or LinkedHashSet. If you lot are asked to save the companionship of elements, hence you lot tin displace use LinkedHashSet, every bit it maintains the companionship 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);      // ready volition decline 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 lot run this programme every bit JUnit bear witness inwards Eclipse, you lot volition come across a greenish bar similar below which indicates that all bear witness cases are passed together with our solution is working fine.

This is a skillful solution together with also shows how the intelligent role of a data structure tin displace brand the solution easy. The code is real tardily to read together with sympathise together with it's also real efficient inwards price of CPU fourth dimension every bit you lot only demand O(n) fourth dimension to solve this problem.

Btw, if interviewer even hence seat to a greater extent than or less other constraint together with inquire you lot to withdraw duplicates without using Java Collection API hence you lot direct hold no selection but to iterate over an array together with compare each together with every chemical cistron to uncovering together with withdraw duplicates.  The full solution is discussed here, which you lot tin displace also come across after you lot direct hold tried.


That's all well-nigh how to withdraw duplicates from an unsorted array inwards Java. Every solution is acceptable but all has its pros together with cons. The fundamental matter is that you lot should start amongst the solution amongst the highest fourth dimension together with infinite complexity together with hence achieve to the most efficient one. This is ane of the technique I ever role on interviews amongst bringing the interviewer to my potent areas.

Further Learning
Data Structures together with Algorithms: Deep Dive Using Java
solution]

Write a programme to uncovering top 2 numbers from an integer array? [solution]

30+ Array-based Coding Problems from Interviews (questions)

How to banking concern fit if an array contains a release inwards Java? [solution]

How create you lot withdraw duplicates from an array inwards place? [solution]

How to uncovering the largest together with smallest release from a given array inwards Java? [solution]

10 Free Data Structure together with Algorithms Courses for Programmers [courses]

Write a programme to uncovering the missing release inwards integer array of 1 to 100? [solution]

How create you lot contrary an array inwards house inwards Java? [solution]

How to uncovering the maximum together with minimum release inwards an unsorted array? [solution]

10 Algorithms courses to Crack Coding Interviews [courses]

How to form an array inwards house using QuickSort algorithm? [solution]

How create you lot impress all duplicate elements from the array inwards Java? [solution]

50+ Data Structure together with Algorithms Coding Problems from Interviews (questions)

10 Algorithms Books Every Programmer should read [books]

Thanks for reading this article. If you lot similar this interview inquiry hence delight portion amongst your friends together with colleagues. If you lot direct hold whatsoever doubtfulness or feedback hence delight driblet a note.

P. S. - If you lot are looking for to a greater extent than or less Free Algorithms courses to improve your agreement of Data Structure together with Algorithms, hence you lot should also banking concern fit this listing of Free Data Structure together with Algorithms Courses for Programmers.