How to Remove Duplicates from Array without Using Java Collection API? Example (original) (raw)

This is a coding question recently asked to one of my readers in a Java Technical interview on investment bank. The question was to remove duplicates from an integer array without using any collection API classes like Set, HashSet, TreeSet or LinkedHashSet, which can make this task trivial. In general, if you need to do this for any project work, I suggest better using the Set interface, particularly LinkedHashSet, because that also keeps the order on which elements are inserted into Set. Why Set? because it doesn't allow duplicates and if you insert duplicate the add() method of Set interface will return false.

Now coming to this coding problem, only from a technical interview perspective, you need to do this using either loops or recursion, depending upon what is your strongest area.

In this article, I am sharing a naïve solution, which has lots of limitations to be considered as production quality code, it's not the best solution but still a solution to start with.

The main problem, while dealing with an array is not finding duplicates, it's about removing them. Since an array is a static, fixed-length data structure, you can not change its length of array once created.

This means, deleting an element from an array requires creating a new array and copying content into that array.

If your input array contains lots of duplicates then this may result in lots of temporary arrays. It also increases the cost of copying content, which can be very bad. Given this restriction, you need to come out with a strategy to minimize both memory and CPU requirements.

Java Program to remove duplicates from integer array without Collection

In this program, we have not used any collection class to remove duplicates, earlier, I had shown you a way to remove duplicates from ArrayList, which was using LinkedHashSet. You can still use that solution if the interviewer doesn't mention it without Collection specifically.

All you need to do is to convert your array into ArrayList first then subsequently create a LinkedHashSet from that ArrayList.

In this example, we are removing duplicates from the array by not copying them into the result array, this solution is not actually deleting duplicates instead it replacing them with the default value i.e. zero.

How to Remove Duplicates from Array Without Using Java Collection API? Example

Now, let's see our Java solution for removing duplicates from integer array:

import java.util.Arrays;

import org.slf4j.Logger;

import org.slf4j.LoggerFactory;

/**

* Java program to remove duplicates from this array. You don't

* need to physically delete duplicate elements, replacing with null, or

* empty or default value is ok.

*

* @author http://javarevisited.blogspot.com

*/

public class TechnicalInterviewTest {

private static final Logger logger = LoggerFactory.getLogger(TechnicalInterviewTest.class);

public static void main(String args[]) {

int[][] test = new int[][]{

{1, 1, 2, 2, 3, 4, 5},

{1, 1, 1, 1, 1, 1, 1},

{1, 2, 3, 4, 5, 6, 7},

{1, 2, 1, 1, 1, 1, 1},};

for (int[] input : test) {

System.out.println("Array with Duplicates : " + Arrays.toString(input));

System.out.println("After removing duplicates : " + Arrays.toString(removeDuplicates(input)));

}

}

/*

* Method to remove duplicates from array in Java, without using

* Collection classes e.g. Set or ArrayList. Algorithm for this

* method is simple, it first sort the array and then compare adjacent

* objects, leaving out duplicates, which is already in the result.

*/

public static int[] removeDuplicates(int[] numbersWithDuplicates) {

// Sorting array to bring duplicates together

Arrays.sort(numbersWithDuplicates);

int[] result = new int[numbersWithDuplicates.length];

int previous = numbersWithDuplicates[0];

result[0] = previous;

for (int i = 1; i < numbersWithDuplicates.length; i++) {

int ch = numbersWithDuplicates[i];

if (previous != ch) {

result[i] = ch;

}

previous = ch;

}

return result;

}

}

Output :

Array with Duplicates : [1, 1, 2, 2, 3, 4, 5]

After removing duplicates : [1, 0, 2, 0, 3, 4, 5]

Array with Duplicates : [1, 1, 1, 1, 1, 1, 1]

After removing duplicates : [1, 0, 0, 0, 0, 0, 0]

Array with Duplicates : [1, 2, 3, 4, 5, 6, 7]

After removing duplicates : [1, 2, 3, 4, 5, 6, 7]

Array with Duplicates : [1, 2, 1, 1, 1, 1, 1]

After removing duplicates : [1, 0, 0, 0, 0, 0, 2]

That's all about how to remove duplicates from an array in Java without using the Collection class. As I said before, this solution is not perfect and has some serious limitations, which is an exercise for you to find out, but it should work in coding interview

Java Program to remove duplicates from Integer array without CollectionOne hint I can give is that the array itself can contain default values as duplicates e.g. 0 for int, even if you use any Magic number like Integer.MAX_VALUE, you can not be certain that they will not be part of the input.

Regarding removing duplicates permanently from the result array, one approach could be to count a number of duplicates and then create an array of the right size i.e. length - duplicates, and then copying content from the intermediate result array to the final array, leaving out elements which are marked duplicate.

In fact you can first start with this solution and they start optimizing it and discussing its limitation, as per my experience, interviewer really likes that kind of discussion and approach instead of seeing the perfect solution.

So, its a good strategy not to give perfect solution at the start on interview as most of the time they think you have seen the problem before.

Related Data Structure and Algorithm Interview Questions from Javarevisited Blog