Objective: Given an array of integers, find out duplicates in it.
Example:
int [] a = {4, 6, 2, 1, 2, 5}; Output: Array has duplicates : 2 int a [] = {1, 6, 5, 2, 3, 3, 2}; Output: Array has duplicates : 2 , 3
Approach:
Naive approach: Use 2 loops. Check each element in the array with all other elements in the array and check if it has the same value.
Time Complexity : O(n^2) Space Complexity: O(1)
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Arrays; | |
public class CheckDuplicatesUsingTwoLoops { | |
public void hasDuplicates2ForLoops(int [] arrA) { | |
for (int i = 0; i < arrA.length; i++) { | |
for (int j = i+1; j < arrA.length; j++) { | |
if(arrA[i]==arrA[j]){ | |
System.out.println("Array has duplicates : " + arrA[i]); | |
} | |
} | |
} | |
} | |
public static void main(String[] args) { | |
int a [] = {1, 6, 5, 2, 3, 3, 2}; | |
new CheckDuplicatesUsingTwoLoops().hasDuplicates2ForLoops(a); | |
} | |
} |
Sorting approach: Sort the array, this will bring all the duplicates together if present. Now navigate the array and check the adjacent elements to check for duplicates.
Time Complexity : O(nlogn) Space Complexity: O(n) by using merge sort.
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Arrays; | |
public class CheckDuplicatesUsingSorting { | |
public void hasDuplicatesUsingSorting(int [] arrA) { | |
Arrays.sort(arrA); | |
for (int i = 0; i < arrA.length–1; i++) { | |
if(arrA[i]==arrA[i+1]){ | |
System.out.println("Array has duplicates : " + arrA[i]); | |
} | |
} | |
} | |
public static void main(String[] args) { | |
int a [] = {1, 6, 5, 2, 3, 3, 2}; | |
new CheckDuplicatesUsingSorting().hasDuplicatesUsingSorting(a); | |
} | |
} |
Better Solution : Use Hash map. Store the count of each element of array in a hash table and later check in Hash table if any element has count more than 1. ( Similar approach is used in problem – Find the first non repeating character in a given string
Time Complexity : O(n) and Space Complexity: O(n).
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
import java.util.Arrays; | |
import java.util.HashMap; | |
public class CheckDuplicatesUsingHashMap { | |
public void hasDuplicatesUsingMap(int [] arrA){ | |
HashMap<Integer, Integer> map = new HashMap<>(); | |
for (int i = 0; i <arrA.length ; i++) { | |
if(map.containsKey(arrA[i])){ | |
System.out.println("Array has duplicates : " + Math.abs(arrA[i])); | |
}else{ | |
map.put(arrA[i], 1); | |
} | |
} | |
} | |
public static void main(String[] args) { | |
int a [] = {1, 6, 5, 2, 3, 3, 2}; | |
new CheckDuplicatesUsingHashMap().hasDuplicatesUsingMap(a); | |
} | |
} |
Better Solution (Conditional) : O(n) time and O(1) extra space.
- This solution works only if array has positive integers and all the elements in the array are in range from 0 to n-1 where n is the size of the array.
- Navigate the array.
- Update the array as for ith index :- arrA[arrA[i]] = arrA[arrA[i]]*-1 (if it already not negative).
- If is already negative, we have duplicates, return false.
Note:
- The code given below does not handle the case when 0 is present in the array.
- To handle 0 in array, while navigating the array, when 0 is encountered, replace it with INT_MIN and if INT_MIN is encountered while traversing, this means 0 is repeated in the array.
Similar approach used in problem : If array has all consecutive numbers.
Code:
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
public class CheckDuplicates { | |
public void hasDuplicates(int[] arrA) { | |
for (int i = 0; i < arrA.length; i++) { | |
//check if element is negative, if yes the we have found the duplicate | |
if (arrA[Math.abs(arrA[i])] < 0) { | |
System.out.println("Array has duplicates : " + Math.abs(arrA[i])); | |
} else { | |
arrA[Math.abs(arrA[i])] = arrA[Math.abs(arrA[i])] * –1; | |
} | |
} | |
} | |
public static void main(String[] args) { | |
int a[] = {1, 6, 5, 2, 3, 3, 2}; | |
new CheckDuplicates().hasDuplicates(a); | |
} | |
} |
Output:
Array has duplicates : 3 Array has duplicates : 2