How To Take Away Duplicates From Array Without Using Coffee Collection Api

This is a coding inquiry of late asked to ane of my readers inwards a Java Technical interview. Question was to take away duplicates from an integer array without using whatsoever collection API classes similar Set or LinkedHashSet, which tin displace brand this draw trivial. In general, if yous demand to do this for whatsoever projection work, I advise ameliorate using Set interface, specially LinkedHashSet, because that too proceed the guild on which elements are inserted into Set. Only for technical interview perspective, yous demand to do this using either loops or recursion,  depending upon what is your strongest area. In this article, I am sharing a naive solution, which has lots of limitation to live on considered equally production character code, It's non the best solution simply withal a solution.

The primary problem, spell dealing amongst an array is non finding duplicates, it's close removing them. Since an array is a static, fixed length information structure, yous tin displace non alter its length. This means, deleting an chemical factor from an array requires creating a novel array as well as copying content into that array.

If your input array contains lots of duplicates as well as hence this may effect inwards lots of temporary arrays. It too increases toll of copying contents, which tin displace live on really bad. Given this restriction, yous demand to come upward out amongst a strategy to minimize both memory as well as CPU requirements.

Java Program to take away duplicates from integer array without Collection

take away duplicates from ArrayList, which was using LinkedHashSet. You tin displace withal usage that solution if the interviewer doesn't lift without Collection specifically.

All yous demand to do is to convert your array into ArrayList starting fourth dimension as well as hence later do a LinkedHashSet from that ArrayList. In this example, nosotros are removing duplicates from the array yesteryear non copying them into effect array, this solution is non truly deleting duplicates instead it replacing it amongst default value i.e. zero.

You tin displace too run into Cracking the Coding Interview, a collection of 189 coding questions from diverse programming interviews from tech companies similar Amazon, Google, Facebook, as well as Microsoft. That volition assist yous to prepare the coding feel yous demand to solve problems similar this.

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

import java.util.Arrays;

import org.slf4j.Logger;

import org.slf4j.LoggerFactory;

/**

 * Java programme to take away duplicates from this array. You don't

 * demand to physically delete duplicate elements, replacing amongst 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[][] evidence = 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 amongst Duplicates       : " + Arrays.toString(input));

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

        }

    }

    /*

     * Method to take away duplicates from array inwards Java, without using

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

     * method is simple, it starting fourth dimension variety the array as well as and hence compare adjacent

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

     */

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

        // Sorting array to convey duplicates together      

        Arrays.sort(numbersWithDuplicates);     

      

        int[] effect = 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 amongst Duplicates       : [1, 1, 2, 2, 3, 4, 5]

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

Array amongst Duplicates       : [1, 1, 1, 1, 1, 1, 1]

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

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

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

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

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

That's it close how to take away duplicates from an array inwards Java without using Collection class. As I said before, this solution is non perfect as well as has or hence serious limitation, which is an do for yous to abide by out. One hint I tin displace laissez passer on is that array itself tin displace incorporate default value equally duplicates e.g. 0 for int, fifty-fifty if yous usage whatsoever Magic expose e.g. Integer.MAX_VALUE, yous tin displace  not live on certainly that they volition non live on usage of the input.

Regarding removing duplicate permanently from effect array, ane approach could live on to count a expose of duplicates as well as and hence do an array of correct size i.e. length - duplicates, as well as and hence copying content from intermediate effect array to concluding array, leaving out elements which are marked duplicate.


Further Learning
Data Structures as well as Algorithms: Deep Dive Using Java
answer)

Difference betwixt a binary tree as well as binary search tree? (answer)

How to contrary a linked listing inwards Java using iteration as well as recursion? (solution)

How to contrary an array inwards house inwards Java? (solution)

How to abide by all permutations of a String inwards Java? (solution)

How to contrary a String inwards house inwards Java? (solution)

How to take away duplicate elements from an array without using Collections? (solution)

Top five Books on Data Structure as well as Algorithms for Java Developers (books)

Top five books on Programming/Coding Interviews (list)

Share this post