Find Duplicates in Arrays: A Comprehensive Guide

Introduction :

In your Java application, duplicate elements in an array might lead to problems therefore it’s important to know how to detect and get rid of them.

In this blog post, we’ll show you how to find duplicates in array using Java, and provide some tips for optimizing your code for better performance and at the end we will solve one related question from GeeksForGeeks.

Find duplicates in arrays ?

In order to identify duplicate elements in an array, the first step is to loop through the array and then compare each element to every other element.

To do this, a nested loop can be used. Use the equals() method inside the inner loop to compare the current element to the element being compared there. You’ve identified a duplicate if they are identical.

Here is an example of how you can find duplicates in an array using Java:

public static void findDuplicates(int[] arr) {
    for (int i = 0; i < arr.length; i++) {
        for (int j = i + 1; j < arr.length; j++) {
            if (arr[i] == arr[j]) {
                System.out.println("Duplicate: " + arr[i]);
            }
        }
    }
}

In this example, we are using two loops, one inside the other, to compare each element in the array with every other element. If a duplicate is found then it is printed to the console.

Optimized approach :

To optimize the performance of your code, consider using a data structure such as a HashSet to efficiently store the elements as you iteratively traverse the array.

If an element already exists in the HashSet, then it is a duplicate. This approach can reduce the time complexity of your code from O(n^2) to O(n).

//program to find duplicates in array
// Solution by technoname.com

public static void findDuplicates(int[] arr) {
    Set<Integer> set = new HashSet<>();
    for (int i = 0; i < arr.length; i++) {
        if (!set.add(arr[i])) {
            System.out.println("Duplicate: " + arr[i]);
        }
    }
}

Question from GeeksForGeeks Solved :

Given an array a[] of size N which contains elements from 0 to N-1, you need to find all the elements occurring more than once in the given array.

Note: The extra space is only for the array to be returned.
Try and perform all operations within the provided array.

Example 1:

Input:
N = 4
a[] = {0,3,1,2}
Output: -1
Explanation: N=4 and all elements from 0
to (N-1 = 3) are present in the given
array. Therefore output is -1.

Example 2:

Input:
N = 5
a[] = {2,3,1,2,3}
Output: 2 3 
Explanation: 2 and 3 occur more than once
in the given array.

Your Task:
Complete the function duplicates() which takes array a[] and n as input as parameters and returns a list of elements that occur more than once in the given array in a sorted manner. If no such element is found, return list containing [-1].

Expected Time Complexity: O(n).
Expected Auxiliary Space: O(n).

Constraints:
1 <= N <= 10⁵
0 <= A[i] <= N-1, for each valid i

// Solution by technoname.com
//{ Driver Code Starts
import java.io.*;
import java.util.*;
import java.util.Map.Entry;

class GFG {
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int t = sc.nextInt();
        while (t-- > 0) {
            int n = sc.nextInt();
            int[] a = new int[n];
            for (int i = 0; i < n; i++) a[i] = sc.nextInt();
            Solution g = new Solution();
            ArrayList<Integer> ans = g.duplicates(a, n);
            for (Integer val : ans) System.out.print(val + " ");
            System.out.println();
        }
    }
}

// } Driver Code Ends


class Solution {
     public static ArrayList<Integer> duplicates(int arr[], int n) {
      ArrayList<Integer> dup = new ArrayList<Integer>();
      TreeSet<Integer> set =new TreeSet<Integer>();
      int freq[]= new int[n]; 
      for(int i=0;i<n;i++){
           freq[arr[i]]++;      
        }
        for(int i=0;i<n;i++){
            if(freq[arr[i]] >1){
                set.add(arr[i]);
            }  
        }
        if(set.size()>0 ){
         dup.addAll(set);
         return dup;
        }
        else{
        dup.add(-1);
        return dup;
        }
    }
}

Frequently Asked Questions:

What is the purpose of detecting duplicates in arrays?

Detecting duplicates in arrays is important to avoid potential problems in your Java application.

How can duplicates be found in arrays using Java?

You can find duplicates in arrays using Java by looping through the array and comparing each element to every other element using a nested loop and the equals() method.

What is an optimized approach to finding duplicates in arrays?

An optimized approach to finding duplicates in arrays is to use a data structure such as a HashSet to efficiently store the elements as you traverse the array.
If an element already exists in the HashSet, then it is a duplicate.

What is the time complexity of the optimized approach to finding duplicates in arrays?

The time complexity of the optimized approach is O(n), which is much better compared to the time complexity of the non-optimized approach which is O(n^2).

Thank you !!

By reading this article, you can enhance your knowledge and develop your programming skills. We’ve provided insightful suggestions and specific examples for finding duplicates in array in Java.

Please feel free to share any other approaches or methods you may have with us by posting a comment or emailing technonamecontact@gmail.com. Your code can be highlighted on our website.

To further improve your understanding of programming concepts please check out our article on the most frequently asked questions about strings, complete with examples.

This will give you a deeper understanding of string operations and increase your chances of success in an interview.

If you found this article informative and helpful, please share it with your friends and colleagues. If you have any questions or feedback, please feel free to leave a comment or contact us.