Given an array of n integers. The task is to print the duplicates in the given array. If there are no duplicates then print -1.
Examples:
Input: {2, 10,10, 100, 2, 10, 11,2,11,2}
Output: 2 10 11
Input: {5, 40, 1, 40, 100000, 1, 5, 1}
Output: 5 40 1
Note: The duplicate elements can be printed in any order.
Simple Approach: The idea is to use nested loop and for each element check if the element is present in the array more than once or not. If present, then store it in a Hash-map. Otherwise, continue checking other elements.
Below is the implementation of the above approach:
C++
// C++ implementation of the// above approach#include <bits/stdc++.h>using namespace std;// Function to find the Duplicates,// if duplicate occurs 2 times or// more than 2 times in array so, // it will print duplicate value// only once at outputvoid findDuplicates(int arr[], int len){ // Initialize ifPresent as false bool ifPresent = false; // ArrayList to store the output vector<int> al; for(int i = 0; i < len - 1; i++) { for(int j = i + 1; j < len; j++) { if (arr[i] == arr[j]) { // Checking if element is // present in the ArrayList // or not if present then break auto it = std::find(al.begin(), al.end(), arr[i]); if (it != al.end()) { break; } // If element is not present in the // ArrayList then add it to ArrayList // and make ifPresent at true else { al.push_back(arr[i]); ifPresent = true; } } } } // If duplicates is present // then print ArrayList if (ifPresent == true) { cout << "[" << al[0] << ", "; for(int i = 1; i < al.size() - 1; i++) { cout << al[i] << ", "; } cout << al[al.size() - 1] << "]"; } else { cout << "No duplicates present in arrays"; }}// Driver codeint main(){ int arr[] = { 12, 11, 40, 12, 5, 6, 5, 12, 11 }; int n = sizeof(arr) / sizeof(arr[0]); findDuplicates(arr, n); return 0;}// This code is contributed by divyeshrabadiya07 |
Java
// Java implementation of the// above approachimport java.util.ArrayList;public class GFG { // Function to find the Duplicates, // if duplicate occurs 2 times or // more than 2 times in // array so, it will print duplicate // value only once at output static void findDuplicates( int arr[], int len) { // initialize ifPresent as false boolean ifPresent = false; // ArrayList to store the output ArrayList<Integer> al = new ArrayList<Integer>(); for (int i = 0; i < len - 1; i++) { for (int j = i + 1; j < len; j++) { if (arr[i] == arr[j]) { // checking if element is // present in the ArrayList // or not if present then break if (al.contains(arr[i])) { break; } // if element is not present in the // ArrayList then add it to ArrayList // and make ifPresent at true else { al.add(arr[i]); ifPresent = true; } } } } // if duplicates is present // then print ArrayList if (ifPresent == true) { System.out.print(al + " "); } else { System.out.print( "No duplicates present in arrays"); } } // Driver Code public static void main(String[] args) { int arr[] = { 12, 11, 40, 12, 5, 6, 5, 12, 11 }; int n = arr.length; findDuplicates(arr, n); }} |
Python3
# Python3 implementation of the# above approach# Function to find the Duplicates,# if duplicate occurs 2 times or# more than 2 times in array so,# it will print duplicate value # only once at outputdef findDuplicates(arr, Len): # Initialize ifPresent as false ifPresent = False # ArrayList to store the output a1 = [] for i in range(Len - 1): for j in range(i + 1, Len): # Checking if element is # present in the ArrayList # or not if present then break if (arr[i] == arr[j]): if arr[i] in a1: break # If element is not present in the # ArrayList then add it to ArrayList # and make ifPresent at true else: a1.append(arr[i]) ifPresent = True # If duplicates is present # then print ArrayList if (ifPresent): print(a1, end = " ") else: print("No duplicates present in arrays")# Driver Codearr = [ 12, 11, 40, 12, 5, 6, 5, 12, 11 ] n = len(arr)findDuplicates(arr, n)# This code is contributed by rag2127 |
C#
// C# implementation of the// above approachusing System;using System.Collections.Generic; class GFG{ // Function to find the Duplicates,// if duplicate occurs 2 times or// more than 2 times in array so, // it will print duplicate value // only once at outputstatic void findDuplicates(int[] arr, int len){ // Initialize ifPresent as false bool ifPresent = false; // ArrayList to store the output List<int> al = new List<int>(); for(int i = 0; i < len - 1; i++) { for(int j = i + 1; j < len; j++) { if (arr[i] == arr[j]) { // Checking if element is // present in the ArrayList // or not if present then break if (al.Contains(arr[i])) { break; } // If element is not present in the // ArrayList then add it to ArrayList // and make ifPresent at true else { al.Add(arr[i]); ifPresent = true; } } } } // If duplicates is present // then print ArrayList if (ifPresent == true) { Console.Write("[" + al[0] + ", "); for(int i = 1; i < al.Count - 1; i++) { Console.Write(al[i] + ", "); } Console.Write(al[al.Count - 1] + "]"); } else { Console.Write("No duplicates present in arrays"); }}// Driver code static void Main(){ int[] arr = { 12, 11, 40, 12, 5, 6, 5, 12, 11 }; int n = arr.Length; findDuplicates(arr, n);}}// This code is contributed by divyesh072019 |
Javascript
<script>// JavaScript implementation of the// above approach// Function to find the Duplicates,// if duplicate occurs 2 times or// more than 2 times in// array so, it will print duplicate// value only once at outputfunction findDuplicates(arr, len) { // initialize ifPresent as false let ifPresent = false; // ArrayList to store the output let al = new Array(); for (let i = 0; i < len - 1; i++) { for (let j = i + 1; j < len; j++) { if (arr[i] == arr[j]) { // checking if element is // present in the ArrayList // or not if present then break if (al.includes(arr[i])) { break; } // if element is not present in the // ArrayList then add it to ArrayList // and make ifPresent at true else { al.push(arr[i]); ifPresent = true; } } } } // if duplicates is present // then print ArrayList if (ifPresent == true) { document.write(`[${al}]`); } else { document.write("No duplicates present in arrays"); }}// Driver Codelet arr = [12, 11, 40, 12, 5, 6, 5, 12, 11];let n = arr.length;findDuplicates(arr, n);</script> |
Output
[12, 11, 5]
Time Complexity: O(N2)
Auxiliary Space: O(N)
Efficient Approach: Use unordered_map for hashing. Count frequency of occurrence of each element and the elements with frequency more than 1 is printed. unordered_map is used as range of integers is not known. For Python, Use Dictionary to store number as key and it’s frequency as value. Dictionary can be used as range of integers is not known.
Below is the implementation of the above approach:
C++
// C++ program to find// duplicates in the given array#include <bits/stdc++.h>usingnamespacestd;// function to find and print duplicatesvoidprintDuplicates(intarr[],intn){// unordered_map to store frequenciesunordered_map<int,int> freq;for(inti=0; i<n; i++)freq[arr[i]]++;booldup =false;unordered_map<int,int>:: iterator itr;for(itr=freq.begin(); itr!=freq.end(); itr++){// if frequency is more than 1// print the elementif(itr->second > 1){cout << itr->first <<" ";dup =true;}}// no duplicates presentif(dup ==false)cout <<"-1";}// Driver program to test aboveintmain(){intarr[] = {12, 11, 40, 12, 5, 6, 5, 12, 11};intn =sizeof(arr) /sizeof(arr[0]);printDuplicates(arr, n);return0;}Java
// Java program to find// duplicates in the given arrayimportjava.util.HashMap;importjava.util.Map;importjava.util.Map.Entry;publicclassFindDuplicatedInArray{// Driver programpublicstaticvoidmain(String[] args){intarr[] = {12,11,40,12,5,6,5,12,11};intn = arr.length;printDuplicates(arr, n);}// function to find and print duplicatesprivatestaticvoidprintDuplicates(int[] arr,intn){Map<Integer,Integer> map =newHashMap<>();intcount =0;booleandup =false;for(inti =0; i < n; i++){if(map.containsKey(arr[i])){count = map.get(arr[i]);map.put(arr[i], count +1);}else{map.put(arr[i],1);}}for(Entry<Integer,Integer> entry : map.entrySet()){// if frequency is more than 1// print the elementif(entry.getValue() >1){System.out.print(entry.getKey()+" ");dup =true;}}// no duplicates presentif(!dup){System.out.println("-1");}}}Python3
# Python3 program to find duplicates# using dictionary approach.defprintDuplicates(arr):dict={}foreleinarr:try:dict[ele]+=1except:dict[ele]=1foritemindict:# if frequency is more than 1# print the elementif(dict[item] >1):(item, end=" ")("\n")# Driver Codeif__name__=="__main__":list=[12,11,40,12,5,6,5,12,11]printDuplicates(list)# This code is contributed# by Sushil BhileC#
// C# program to find// duplicates in the given arrayusingSystem;usingSystem.Collections.Generic;classGFG{// function to find and print duplicatesstaticvoidprintDuplicates(int[] arr,intn){Dictionary<int,int> map =newDictionary<int,int>();intcount = 0;booldup =false;for(inti = 0; i < n; i++){if(map.ContainsKey(arr[i])){count = map[arr[i]];map[arr[i]]++;}elsemap.Add(arr[i], 1);}foreach(KeyValuePair<int,int> entryinmap){// if frequency is more than 1// print the elementif(entry.Value > 1)Console.Write(entry.Key +" ");dup =true;}// no duplicates presentif(!dup)Console.WriteLine("-1");}// Driver CodepublicstaticvoidMain(String[] args){int[] arr = { 12, 11, 40, 12,5, 6, 5, 12, 11 };intn = arr.Length;printDuplicates(arr, n);}}// This code is contributed by// sanjeev2552Javascript
<script>// JavaScript program to find// duplicates in the given array// Function to find and print duplicatesfunctionprintDuplicates(arr, n){// unordered_map to store frequenciesvarfreq =newMap();for(let i = 0; i < n; i++){if(freq.has(arr[i])){freq.set(arr[i], freq.get(arr[i]) + 1);}else{freq.set(arr[i], 1);}}vardup =false;for(let [key, value] of freq){// If frequency is more than 1// print the elementif(value > 1){document.write(key +" ");dup =true;}}// No duplicates presentif(dup ==false)document.write("-1");}// Driver codevararr = [ 12, 11, 40, 12,5, 6, 5, 12, 11 ];varn = arr.length;printDuplicates(arr, n);// This code is contributed by lokeshpotta20</script>
Output
5 12 11
Time Complexity: O(N)
Auxiliary Space: O(N)
Another Efficient Approach(Space optimization):
- First we will sort the array for binary search function.
- we will find index at which arr[i] occur first time lower_bound
- Then , we will find index at which arr[i] occur last time upper_bound
- Then check if diff=(last_index-first_index+1)>1
- If diff >1 means it occurs more than once and print
Below is the implementation of the above approach:
C++
// C++ implementation of the above approach#include <bits/stdc++.h>using namespace std;//Function to Print elements that occurs in arr more than 1void printDuplicates(int arr[], int n){ sort(arr,arr+n);//sort array for binary search cout<<"["; for(int i = 0 ; i < n ;i++) { //index of first and last occ of arr[i]; int first_index = lower_bound(arr,arr+n,arr[i])- arr; int last_index = upper_bound(arr,arr+n,arr[i])- arr-1; int occur_time = last_index-first_index+1;//frequency of arr[i] if(occur_time > 1 )// elements that occur more than 1 { i=last_index; //update i to last_index cout<<arr[i]<<", "; }// print repeat element } cout<<"]";}// Driver codeint main(){ int arr[] = {12, 11, 40, 12, 5, 6, 5, 12, 11}; int n = sizeof(arr) / sizeof(arr[0]); //Function call printDuplicates(arr, n); return 0;}// This Approach is contributed by nikhilsainiofficial546 |
Python3
# Function to print elements that occur in arr more than oncedef printDuplicates(arr, n): arr.sort() # Sort array for binary search print("[", end="") # Print opening bracket i = 0 # Initialize index while i < n: # Index of first and last occurrence of arr[i] first_index = arr.index(arr[i]) last_index = n - arr[::-1].index(arr[i]) - 1 occur_time = last_index - first_index + 1 # Frequency of arr[i] if occur_time > 1: # If element occurs more than once i = last_index # Update i to last index print(arr[i], end=", ") # Print repeat element i += 1 # Increment index print("]") # Print closing bracket# Driver codearr = [12, 11, 40, 12, 5, 6, 5, 12, 11]n = len(arr)# Function callprintDuplicates(arr, n) |
Java
// Java implementation of the above approachimport java.io.*;import java.util.*;class GFG { // Function to find lower bound of target in arr public static int lowerBound(int[] arr, int target) { int lo = 0, hi = arr.length - 1; int ans = -1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] >= target) { ans = mid; hi = mid - 1; } else { lo = mid + 1; } } return ans; } // Function to find upper bound of target in arr public static int upperBound(int[] arr, int target) { int lo = 0, hi = arr.length - 1; int ans = -1; while (lo <= hi) { int mid = lo + (hi - lo) / 2; if (arr[mid] <= target) { ans = mid; lo = mid + 1; } else { hi = mid - 1; } } return ans; } // Function to print elements that occur more than once // in arr static void printDuplicates(int[] arr, int n) { Arrays.sort(arr); // sort array for binary search System.out.print("["); for (int i = 0; i < n; i++) { // index of first and last occ of arr[i] int firstIndex = lowerBound(arr, arr[i]); int lastIndex = upperBound(arr, arr[i]); int occurTime = lastIndex - firstIndex + 1; // frequency of arr[i] if (occurTime > 1) { // elements that occur more than 1 i = lastIndex; // update i to last_index System.out.print(arr[i] + ", "); } } System.out.println("]"); } public static void main(String[] args) { int[] arr = { 12, 11, 40, 12, 5, 6, 5, 12, 11 }; int n = arr.length; // Function call printDuplicates(arr, n); }}// This code is contributed by karthik. |
Javascript
// Javascript implementation:function printDuplicates(arr, n) { // sort array for binary search arr.sort(); console.log("["); for (let i = 0; i < n; i++) { // index of first and last occ of arr[i]; let first_index = arr.indexOf(arr[i]); let last_index = arr.lastIndexOf(arr[i]); let occur_time = last_index - first_index + 1; //frequency of arr[i] if (occur_time > 1) { // elements that occur more than 1 i = last_index; //update i to last_index console.log(arr[i] + ", "); } // print repeat element } console.log("]");}// Driver codelet arr = [12, 11, 40, 12, 5, 6, 5, 12, 11];let n = arr.length;// Function callprintDuplicates(arr, n);// This code is contributed by akashish__ |
C#
// C# implementation of the above approachusing System;class MainClass { static void printDuplicates(int[] arr, int n) { Array.Sort(arr); // Sort the array for binary search Console.Write("["); for (int i = 0; i < n; i++) { // Index of first and last occ of arr[i]; int first_index = Array.IndexOf(arr, arr[i]); int last_index = Array.LastIndexOf(arr, arr[i]); int occur_time = last_index - first_index + 1; // Frequency of arr[i] if (occur_time > 1) { // Elements that occur more than 1 i = last_index; // Update i to last_index Console.Write(arr[i] + ", "); // Print repeat element } } Console.Write("]"); } static void Main() { int[] arr = {12, 11, 40, 12, 5, 6, 5, 12, 11}; int n = arr.Length; // Function call printDuplicates(arr, n); }}// Contributed by adityasha4x71 |
Output
[5, 11, 12, ]
Time Complexity: O(n*log2n)
Auxiliary Space: O(1)
Related Post :
Print All Distinct Elements of a given integer array
Find duplicates in O(n) time and O(1) extra space | Set 1
Duplicates in an array in O(n) and by using O(1) extra space | Set-2
Print all the duplicates in the input string
This article is contributed by Ayush Jauhari. If you like neveropen and would like to contribute, you can also write an article using write.geeksforgeeks.org or mail your article to review-team@geeksforgeeks.org. See your article appearing on the neveropen main page and help other Geeks.
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
