Tuesday, January 3, 2017

How to Remove Duplicates from Array Without Using Java Collection API

This is a coding question recently asked to one of my readers in a Java Technical interview. Question was to remove duplicates from an integer array without using any collection API classes like Set 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 keep the order on which elements are inserted into Set. Only for 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 naive solution, which has lots of limitation to be considered as production quality code, It's not the best solution but still a solution.

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. 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.

Before going for a programming/coding interview, It's absolutely necessary to do as much practice in data structure and algorithm as possible to take advantage of all the knowledge available. You can also join a comprehensive Data Structure and Algorithms course like Data Structures and Algorithms: Deep Dive Using Java on Udemy to fill the gaps in your understanding.




Java Program to remove duplicates from integer array without Collection

Java Program to remove duplicates from Integer array without CollectionIn 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 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 result array, this solution is not actually deleting duplicates instead it replacing it with default value i.e. zero.

You can also see Cracking the Coding Interview, a collection of 189 coding questions from various programming interviews from tech companies like Amazon, Google, Facebook, and Microsoft. That will help you to develop the coding sense you need to solve problems like this.




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 it about how to remove duplicates from an array in Java without using Collection class. As I said before, this solution is not perfect and has some serious limitation, which is an exercise for you to find out. One hint I can give is that array itself can contain default value as duplicates e.g. 0 for int, even if you use any Magic number e.g. Integer.MAX_VALUE, you can  not be certain that they will not be part of the input.

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


Further Learning
Data Structures and Algorithms: Deep Dive Using Java
Algorithms and Data Structures - Part 1 and 2
Data Structures in Java 9 by Heinz Kabutz


Related Data Structure and Algorithm Interview Questions from Javarevisited Blog
  • Difference between array and linked list data structure? (answer)
  • Difference between a binary tree and binary search tree? (answer)
  • How to reverse a linked list in Java using iteration and recursion? (solution)
  • How to reverse an array in place in Java? (solution)
  • How to find all permutations of a String in Java? (solution)
  • How to reverse a String in place in Java? (solution)
  • How to remove duplicate elements from an array without using Collections? (solution)
  • Top 5 Books on Data Structure and Algorithms for Java Developers (books)
  • Top 5 books on Programming/Coding Interviews (list)


59 comments :

Unknown said...

import java.util.Arrays;

public class Removeduplicates {

/**
* @param args
*/
public static void main(String[] args) {
// TODO Auto-generated method stub


int[] a = { 3, 1, 1, 4, 1, 4, 5 };

Arrays.sort(a);
int count = 0;

long start = System.currentTimeMillis();

for (int i = 0; i < a.length; i++) {
if (i + 1 < a.length && a[i] == a[i + 1]) {
count++;
}

}

int[] b = new int[a.length - count];
int c = 0;
for (int j = 0; j < a.length; j++) {
if (j + 1 < a.length && a[j] == a[j + 1]) {

} else {
b[c] = a[j];
c++;
}
}

a = b;
System.out.println(Arrays.toString(a) + "took"
+ (System.currentTimeMillis() - start));

}
}

Anonymous said...

why do u need to sort the the array first ?

Anonymous said...

If the array is not sorted you can have duplicates again after the procedure. So sorting is crucial.

Anonymous said...

int[] in = { 3, 1, 1, 4, 1, 4, 5 };
BitSet filter = new BitSet(in.length);
for (int i = 0; i < in.length; i++) {
if (filter.get(in[i])) {
in[i] = 0;
} else {
filter.set(in[i]);
}
}

Anonymous said...

@Anonymous : Why BitSet here? Why not another Array?

Unknown said...

I think u can compare the element while u r sorting.It could be more convenient.

Anonymous said...

int [] num={25,52,25,65,8,96,8,25};
String s="";
for (int i = 0; i < num.length; i++) {
if(!s.contains(String.valueOf(num[i])))
s+=num[i]+",";
}
String stringArray[]=s.split(",");
int [] uniqnum=new int[stringArray.length];
for (int i = 0; i < stringArray.length; i++)
uniqnum[i]=Integer.parseInt(stringArray[i]);
for (int i = 0; i < uniqnum.length; i++) {
System.out.println(uniqnum[i]);
}

Anonymous said...

import java.util.*;
class rmduplicates
{

public static void main(String args[])
{
String[] s={"sasi","sai","nag","sasi","nag","babu","babu","sai"};
int k=0;
/*String[] s=new String[5];
Scanner sc=new Scanner(System.in);
for(int i=0;i<5;i++)
{
s[i]=sc.next();
}*/
Arrays.sort(s);
k=duplicates(s);
System.out.println("total duplicates:"+k);
for(int i=0;i<s.length;i++)
{
for(int j=i+1;j<s.length;j++)
{
if(s[i]==s[j])
{
copy(s,i,j);
}
}
}
for(int i=0;i<k;i++)
{
System.out.println(s[i]);
}
}
public static void copy(String[] s,int i,int j)
{
for(int k=j;k<s.length-1;k++)
{
s[k]=s[k+1];

}

}
public static int duplicates(String[] s)
{
int k=0;
for(int i=0;i<s.length;i++)
{
for(int j=i+1;j<s.length;j++)
{
if(s[i]==s[j])
{
k++;
}
}
}
return k;
}
}

Unknown said...

public static int[] removeDuplicateNumbers(int[] numbersWithDuplicates) {
Arrays.sort(numbersWithDuplicates);

//Using count to store numbers inside array, this will be incremented only in case i am adding number into array
int count = 0;
int[] result = new int[numbersWithDuplicates.length];
int previouNumber = numbersWithDuplicates[0];
result[count] = previouNumber;


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

if(previouNumber != currentNumber) {
result[++count] = currentNumber;
}
previouNumber = currentNumber;
}

//Here, result is created with original array length, so may be size of new array will be small, hence at the end it will contain 0.
return Arrays.copyOf(result, count+1);

}

Anonymous said...

Why don't you create a second array, iterate over the first and, if the item is not in the second array, add it to the first, else, skip it?
This won't require sort at all, will preserve the order and will be, at most, O(n * log n)...

Pan said...

Here is my solution if no form of Collection is allowed.

// n + nlogn + n + n
public static K[] removeDuplicate2(K[] src){
K[] sorted = Arrays.copyOf(src, src.length);

Arrays.sort(sorted);
K[] des = (K[])Array.newInstance(sorted[0].getClass(), sorted.length);

int jLength = 0;
K currentUniqueItem = null;
for(int i = 0; i < sorted.length; i++){
K current = sorted[i];
if(currentUniqueItem == null){
currentUniqueItem = current;
continue;
}
if(current.equals(currentUniqueItem)){
continue;
}
des[jLength++] = (currentUniqueItem = current);
}
des = Arrays.copyOf(des, jLength);
return des;
}

Anonymous said...

Check this out................this is quite simple and better

static int[] removeDuplicate(int a[]){
int[] c = new int[a.length];
int counter = 0;


for(int i=0;i<a.length;i++){
boolean isDupliate = false;
for(int j=0;j<a.length;j++){
if(a[i]==c[j]){
isDupliate = true;
}
}
if(!isDupliate){
c[counter] = a[i];
counter++;
}
}
int[] result= Arrays.copyOf(c, counter);
Arrays.sort(result);
return result;
}

Unknown said...

void myFunction(int arr[])
{

int size=arr.length;
for(int i=0;i<size;i++)
{
for(int j=i+1;j<size;j++)
{

if(arr[i]==arr[j])
{
arr[j]=arr[size-1];
size--;
}
}
}

for(int a=0;a<size;a++)
{
System.out.print(arr[a]+" ");
}

}

Anonymous said...

Can anyone please suggest me solution in interpreted language like Python, Ruby or JavaScript?

Unknown said...

Class Duplicate
{
public static void main(String []args)
{
int[] arr={1,2,3,1,1,3,5,5,6,8};
Arrays.sort(arr);
for(int i=1;i<arr.length;i++)
{
if(arr[i]==arr[i-1])
{
System.out.println("Duplicate = " + arr);
}
}

}}

Anonymous said...

Hmm..
Just wondering how you would check if the item is not in the second array already? How is this O (n*log n) ?

Anonymous said...

import java.util.Arrays;

public class RemoveDulicatesInArray {

public static void main(String[] args) {
// int[] in = { 3, 1, 1, 4, 1, 4, 5 };
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[] num : test) {
removeArrayDuplicates(num);
System.out.println("\n");
}
}
public static void removeArrayDuplicates(int[] in) {

Arrays.sort(in);
System.out.println("oreginal array=" + Arrays.toString(in));
//find dupes count
int duplicatesCnt = 0;
int prev = in[0];
for (int i = 0; i < in.length - 1; i++) {
if (prev == in[i + 1]) {
duplicatesCnt++;
}
prev = in[i + 1];
}

//get final array After removing duplicates
int cnt = 0;
int[] result = new int[in.length - duplicatesCnt];
prev = in[0];
result[cnt] = prev;
for (int i = 0; i < in.length - 1; i++) {
if (prev != in[i+1]) {
result[++cnt] = in[i+1];
}
prev = in[i + 1];
}

Arrays.sort(result);
System.out.println("After removing duplicates" + Arrays.toString(result));
}
}

Anonymous said...

//In-place removal of duplicates
public static void removeDuplicates(int[] arr){

Arrays.sort(arr);
int size = arr.length;
int duplicates=0;
for(int i=1;i<size-duplicates;i++){
if(arr[i]==arr[i-1]){
for(int k=i;k<size-duplicates-1;k++){
arr[k]=arr[k+1];
}
duplicates++;
}

}
System.out.println("New size of array="+(size-duplicates));
for(int j=0;j<size-duplicates;j++){
System.out.print(arr[j]+",");
}
}

sanjay kumar said...

int a[] = {1,2,4,5,6,7,2,1,4,5,6,7,7,78};
System.out.println("Array contains duplicate elements :"+Arrays.toString(a));
int newArray[] = new int[a.length];
newArray[0] = a[0];
for(int i =1;i<a.length;i++){
boolean elementsExist = false;
for(int j =0;j<newArray.length;j++){
if(newArray[j] != 0 && a[i] == newArray[j]){
elementsExist = true;
}
}
if(!elementsExist){
newArray[i] = a[i];
}
}

System.out.println("Array remove duplicate elements :"+Arrays.toString(newArray));

Raghu said...

public static void main(String[] args)
{
int[] numbers={4,2,5,4,6,3,5,2,6,3,7,3,2};
int intDuplicateCount=0;
int intCounter=0;
boolean blnExists;
for(int i=0;i<numbers.length;i++)
{
for(int j=i+1;j<numbers.length;j++)
{
if(numbers[i]==numbers[j])
{
intDuplicateCount+=1;
break;
}
}
}
int intNewSize=numbers.length-intDuplicateCount;
int[] newArray=new int[intNewSize];
for(int i=0;i<numbers.length;i++)
{
blnExists=false;
for(int j=0;j<newArray.length;j++)
{
if(numbers[i]==newArray[j])
{
blnExists=true;
break;
}
}
if(!blnExists)
{
newArray[intCounter++]=numbers[i];
}
}
for(int i=0;i<newArray.length;i++)
{
System.out.print(newArray[i]+", ");
}
}

Unknown said...
This comment has been removed by the author.
Unknown said...


public static void main(String[] args) {
int array[] = {1,4,4,3,5,6,4,3,1,2,8,6,5};
ArrayList l = new ArrayList();

for (int i = 0; i < array.length; i++){
if(!l.contains(array[i])){
l.add(array[i]);
}
else{
array[i] = 0;
}
}
for (int i =0 ; i< array.length ; i++)
System.out.print(array[i]+" ");
}

Anonymous said...

import java.util.Arrays;

public class RemoveDuplicatesInArray {
public static void main(String[] args) {
int a[] = {5,3,4,8,5,9,10,1};
removeDuplicates(a);
}

private static void removeDuplicates(int[] a) {
Arrays.sort(a);
int[] result = new int[a.length];
int count=0;
for(int i=1;i<a.length;i++){
if(a[i]!=a[i-1]){
result[count]=a[i-1];
count++;
}
if( (i==a.length-1 && a[i-1]!=a[i])){
result[count]=a[i];
}

}
System.out.println(Arrays.toString(result));

}
}

Unknown said...

Integer input[]={1,4,4,4,3,1};
Arrays.sort(input);

for(int i=0;i<input.length-1;i++){
if(input[i]==input[i+1]){
input[i]=0;
}
}
System.out.println(Arrays.toString(input));

Unknown said...

int a []=new int[5];
System.out.println("Enter the array element");
for(int i=0;i<5;i++)
{
Scanner in =new Scanner(System.in);
a[i]=in.nextInt();
}
int dub;
for(int i=0;i<a.length;i++)
{
int flag=0;
dub=a[i];
for(int j=i+1;j<a.length;j++)
{
if(dub==a[j])
{
System.out.println(dub);
flag=1;
break;
}
}
if(flag==1)
{
break;
}

}

Diarmuid said...

public static int[] removeDuplicates(int [] a) {
TreeSet<Integer> set = new TreeSet<Integer>();
for(int i : a) {
set.add(i);
}
int [] result = new int[set.size()];
Iterator<Integer> it = set.iterator();
for(int i = 0; i< result.length; i++) {
result[i] = set.pollFirst();
}
return result;
}

Learn Salesforce said...

If you having all String /array Programs which are frequently ask in interview please send
Pdf/doc /link

Seleniumbegginerschoice said...

public static void main(String[] args)
{
int[] ram = {1,12,4,1,55,1,5,64,5,5,6,64,8};
for (int i = 0; i < ram.length ; i++) {
for (int j = 0; j < ram.length; j++) {
if (ram[i] == ram[j])
{
System.out.println("Duplicate numbes of an array is" + ram[i]);
}
}
}

}

Anonymous said...

public static void main(String[] args) {
int [] arr = new int [] {1, 1, 2, 2, 3, 4, 5};
Integer[] result = removeDuplicates(arr);
for (Integer num : result) {
System.out.println(num);
}
}

static Integer[] removeDuplicates(int[] arr) {
List result = new ArrayList<>();
int prev = arr[0];
result.add(prev);

for(int i=1; i<arr.length;i++) {
int current = arr[i];
if(prev!=current) {
result.add(current);
}
prev = current;
}
return result.toArray(new Integer[result.size()]);
}

Unknown said...

import java.util.*;
import java.io.*;

public class ArrDupRmv
{
public static void main(String args[])
{
Scanner sc=new Scanner(System.in);
int a[]=new int[100];
int i,j;
System.out.println("How Many Numbers you Have");
int n=sc.nextInt();
System.out.println("Enter Numbers:");
for(i=0;i<n;i++)
{
a[i]=sc.nextInt();
}
for(i=0;i<n;i++)
{
for(j=i+1;j<n;j++)
{
if(j<n)
{
if(a[i]==a[j])
{
a[j]=0;
}
}
}
}
for(i=0;i<n;i++)
{
System.out.print("\t"+a[i]);
}

}
}

HasanSajedi said...

import numpy as np
from collections import Counter

data1 = np.array([1, 4, 5, 6, 4, 8, 1, 9])
print([item for item, count in Counter(data1).items() if count > 1])

Unknown said...

package array;

import java.util.Arrays;

public class RemoveDuplicateWithoutCollection {

public static void main(String[] args) {
// TODO Auto-generated method stub
int duplicateArray[][] = new int[][] {
{1,2,6,1,7},
{4,6,12,6,8}
};
for(int ar[]: duplicateArray) {
System.out.println(Arrays.toString(removeDuplicate(ar)));
//removeDuplicate(ar);
}
}

public static int[] removeDuplicate(int array[]) {
Arrays.sort(array);
int result[] = new int[array.length];
int previous = result[0] = array[0];
int count = 1;
//System.out.println("result " + Arrays.toString(result));
for(int i = 1,j = 1; i < array.length; i++){
if(previous !=array[i]) {
result[j++] = array[i];
count++;
}
previous = array[i];
}
int uniquearray[] = new int[count];
for(int i = 0; i< count; i++) {
uniquearray[i] = result[i];
}
//System.out.println(Arrays.toString(uniquearray));
//System.out.println(Arrays.toString(result));
return uniquearray;
}

}

maxim said...

public static void main(String[] args) {
int[] r = new int[] {1,3,3,4,6,4,3,4,5,7,5,8};
int[] sortedArr = sorting(r);
for(int cc: sortedArr){
System.out.println(cc+"");
}
}
public static int[] sorting(int[] arr) {
Arrays.sort(arr);
int[] noDuplicates = IntStream.of(arr).distinct().toArray();
return noDuplicates;
}

Unknown said...

public static void main(String[] args) {
Set set = Arrays.stream(new int[]{3, 1, 3, 4, 6, 4, 3, 4, 5, 7, 5, 8}).boxed().collect(Collectors.toSet());
set.stream().forEach(System.out::println);
}

Learn From Java said...

package com.corejava.helloworld.string;
/**
*
* @author balagopalam_n
*
*/
public class RemoveDuplicates {

public static void main(String[] args) {
// without any api
String str = "Java is always Java, hello world is world and is always world";
String[] arr = str.split("[ ]");

String result = "";
for (int i = 0; i < arr.length; i++) {
for (int j = i + 1; j < arr.length; j++) {
if (arr[i] == arr[j]) {

} else {
if (!result.contains(arr[j])) {
result = result + " " + arr[j];
}
}

}
}
if (!result.isEmpty())
System.out.println("After remove duplicates from given string : "
+ result);
else
System.out.println("After remove duplicates from given string : "
+ str);

}
}

Learn From Java said...

//with collections api

String str1= "John is always John and want to be always John";
String[] array = str1.split(" ");
List list = Arrays.asList(array);
Set set = new LinkedHashSet(list);
System.out.println("\""+str1 +"\" after removing duplicates :");
for(String s: set) {
System.out.print(s +" ");
}

thuhpatrick said...

No idea why you're setting all of the same elements to zero, and not just the duplicates. This way is very simple.

import java.util.Arrays;

public class Main {

public static void main(String[] args) {
int[] myArray = new int[]{1, 2, 3, 4, 5, 6, 7, 7, 8, 8, 8, 9};
groupDuplicates(myArray);
}

public static int[] groupDuplicates(int[] myArray) {
Arrays.sort(myArray);
int[] myNewArray = Arrays.copyOf(myArray, myArray.length);
for (int i = 0; i < myArray.length - 1; i++) {
if (myArray[i] == myArray[i + 1]) {
// find duplicates
System.out.println("Number found: " + myArray[i]);
// set duplicates to 0
myNewArray[i] = 0;
}
}
System.out.println(Arrays.toString(myNewArray));
return myNewArray;
}
}

Unknown said...

public class MyClass {
public static void main(String args[]) {
int[] array = {5,4,5,3,8,9,2,1,8,3};
int size=array.length-1;

for(int i=0;i<size;i++){

for(int j=i+1;j<size;j++){

if(array[i]==array[j]){
for(int k=j; k<size; k++)
{
array[k] = array[k + 1];
}
size--;
j--;
}

}
}
for(int i=0; i<size; i++)
{
System.out.println(""+ array[i]);
}
}
}

Output :

5
4
3
8
9
2
1

Sagar Raval said...

// Finding Duplicates in Array(Sorted)


public class _02
{
public static void main(String[] args)
{
int A[]={1,2,2,3,4,4,4};
int B[]={0,0,0,0};
int i,j;

//printing array(A)
for(i=0;i<A.length;i++)
{
System.out.println(A[i]);
}
System.out.println();

//assigning counts in anoter array(B)
for(i=0;i<A.length;i++)
{
for(j=A[i]-1;j<B.length;j++)
{
if(A[i]==j+1)
{
B[A[i]-1]++;
}
}
}

//printing duplicates
for(i=0;i<B.length;i++)
{
if(B[i]!=1)
{
System.out.println((i+1)+" is being duplicated by "+(B[i]-1)+" times");
}
}
}
}

javin paul said...

Good Job @Sagar, how about writing some unit tests?

Sagar Raval said...

Thank you @javin, but what kind of unit test are you talking about exactly?

javin paul said...

test which shows that solution works for different input e.g. array without duplicates, array with one duplicates, array with multiple duplicates, array with just duplicates, empty array, array with one element etc. Nowadays, Interviewer are also focusing on TDD (Test driven development) which encourage to write test first than solution.

Sumedha said...

import java.lang.reflect.Array;
import java.util.Arrays;

public class DuplicateNumber {
public static void main(String[] args){
int[] numbers ={1,3,2,1,4,5,4};
int size = numbers.length;
int[] newnum = new int[size];


for (int i= 0; i<size; i++){

for(int j=i+1;j<size;j++){
if(numbers[i]==numbers[j]){

numbers[j]=numbers[j+1];
size = size-1;
break;

}

}
newnum[i]=numbers[i];

}
System.out.println(Arrays.toString(newnum));
}
}

Unknown said...

public static void main(String args[]) {
int[] arr = { 1, 2, 3, 4, 5, 6, 4, 3, 8,8,9 };
int dupNum;
Arrays.sort(arr);
for (int i = 1; i < arr.length; i++) {

if (arr[i] == arr[i - 1]) {
dupNum = arr[i];
System.out.println(dupNum);

}
}

}

Unknown said...

public static void main(String args[]) {
int[] arr = { 2,1, 2, 3, 4, 5,3, 6, 7, 8, 9, 10 };
int exDupNum;
Arrays.sort(arr);
System.out.println(arr[0]);
for (int i = 1; i < arr.length; i++) {

if ((arr[i] != arr[i-1])) {
exDupNum=arr[i];
System.out.println(exDupNum);

}

}

}

Unknown said...

sir please suggest your solutions for begineers also .

javin paul said...

Hello @Unknwn, can you elaborate please, beginner can also use this solution.

Unknown said...

public class RemoveDuplicates {

public static void main(String[] args) {
System.out.println("To remove duplicates!");

int[] arr = {1,4, 2, 1,3,3,2};
removeDup(arr);

}

public static void removeDup(int[] arr)
{

//Instantiate a List to store all the values of array elements
List list = new ArrayList();
Arrays.sort(arr);

//Add array elements to the list
for(int k=0; k<arr.length; k++)
{
list.add(arr[k]);
}


//if the first and second element in an array are equal then remove the elment from the list
for(int i=0; i<list.size(); i++)
{
for(int j=i+1; j<list.size(); j++)
{
if(list.get(i) == list.get(j))
{
list.remove(j);
}
}
}

Kennedy said...

/** How to Remove Duplicates from Array Without Using Java Collection API
* @author Kennedy
* @ email: jambotechsolutions@gmail.com
*/

import java.util.Arrays;

public class GFG {

// Function to remove the element
public static int[] removeTheElement(int[] arr,
int index)
{

// If the array is empty
// or the index is not in array range
// return the original array
if (arr == null
|| index < 0
|| index >= arr.length) {

return arr;
}

// Create another array of size one less
int[] anotherArray = new int[arr.length - 1];

// Copy the elements from starting till index
// from original array to the other array
System.arraycopy(arr, 0, anotherArray, 0, index);

// Copy the elements from index + 1 till end
// from original array to the other array
System.arraycopy(arr, index + 1,
anotherArray, index,
arr.length - index - 1);

// return the resultant array
return anotherArray;
}

// Driver Code
public static void main(String[] args)
{
// Get the array
int[] arr = { 1, 1, 2, 3, 4, 4, 5, 6, 7, 8, 8, 9, 9, 10 };
//sort array
Arrays.sort(arr);
// Print the resultant array
System.out.println("Original Array: "
+ Arrays.toString(arr));

// Remove the duplicate elements
for(int i = 1; i<arr.length; i++){

if(arr[i] == arr[i-1])
{
arr = removeTheElement(arr, i);
}}

// Print the resultant array
System.out.println("Resultant Array: "
+ Arrays.toString(arr));
}
}

OUTPUT
$javac GFG.java
$java -Xmx128M -Xms16M GFG
Original Array: [1, 1, 2, 3, 4, 4, 5, 6, 7, 8, 8, 9, 9, 10]
Resultant Array: [1, 2, 3, 4, 5, 6, 7, 8, 9, 10]

javin paul said...

great job, how about refactoring this program and separate testing as Unit test?

Kennedy said...

@Javin paul : I think that's exactly what I need to do
Let me also take this opportunity to thank you for creating this wonderful developers community. I have online code challenge with a big company and thus I am practicing here... Be blessed :)

Kennedy said...

@ javin paul : When asked that question "how about refactoring this program and separate testing as Unit test?" What exactly am I supposed to do?

javin paul said...

Hello @Kennedy, currently you are doing testing in your main method, which is just testing one case. It would be better if you encapsulate logic in one class and then another class for JUnit test and then create multiple test method for different test cases like empty array, array without duplicates, array with few duplicates, and array with all duplicates. Hope this is clear. For an example, check this tutorial of mine where I have create unit test for linked list https://javarevisited.blogspot.com/2015/02/simple-junit-example-unit-tests-for-linked-list-java.html

arpit said...

Use bit manioulation

int counter =0;

if(counter & counter << 1 << val > 0 //then its duplicate

else {
counter != (counter << 1 << val )
}

javin paul said...

Hello arpit, can you explain the code little bit for people who are not familiar with bit wise manipulation?

Anonymous said...

int [] intArray = {1,2,5,6,99,88,99,25,33,33,66,41,41};
LinkedHashSet lhs = new LinkedHashSet();
for(Integer in : intArray)
{
lhs.add(in);
}
Object[] updatedArray = lhs.toArray();
for(int i=0;i<updatedArray.length;i++)
{
System.out.println(updatedArray[i]);
}

javin paul said...

Nice one, keep it up

Kuldeep Singh said...

What about this, can't we overcome the space waste using this. Time complexity will still be O(n)

public static void main(String[] args) {
int[] arr = { 1, 2, 3, 3, 4, 5, 6, 2 };
int[] duplicates = findDuplicates(arr);
int[] unique = removeDuplicates(arr);
System.out.println(Arrays.toString(duplicates));
System.out.println(Arrays.toString(unique));

}

private static int[] removeDuplicates(int[] arr) {
Arrays.sort(arr);
String unique = "";
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] != arr[i + 1]) {
unique += arr[i];
}
}
return Stream.of(unique).mapToInt(Integer::parseInt).toArray();
}

private static int[] findDuplicates(int[] arr) {
Arrays.sort(arr);
String duplicates = "";
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] == arr[i + 1]) {
duplicates += arr[i];
}
}
return Stream.of(duplicates).mapToInt(Integer::parseInt).toArray();
}

javin paul said...

Yes, but time complexity will be increased by K

Post a Comment