Given an array. Find duplicate elements in that array.
Solution:
(Note: we assume that the range is not provided and the array can contain both negative and positive numbers. The length of the given array is n. To find duplicates in array with given range visit here).
The solution can be achieved with two ways:
1) By improving the run time but sacrificing the space time.
2) By improving the space time by sacrificing the run time.
Solution 1: Run time : O(n), space time: O(n).
This can be achieved by using a hash map. The following steps are involved for achieving the solution
i) Iterate through array and store all elements in a hash map with key = element, value = no of occurrence.
we store the occurrence in value to avoid printing the same duplicate element again as we iterate through
the array. We will increment the counter of value for each occurrence of the element. So that if the value
of the element is more than 1, means we already encountered the duplicate elements and it is printed in
previous iterations.(e.g. if array contains duplicate value 10 times, program will print duplicate value only
once).
ii) If the element is already present in the hash map (i.e. that element is already encountered while reading array) and the occurrence of that element is 0 (means we encountered the duplicate element for first time), print that element (duplicate element).
Java Implementation:
import java.util.HashMap;
/*
* Program to find duplicate elements in an array.
*/
public class FindDuplicatesInArray {
/*
* Method to find duplicates in array.
*
* @param: Array for which the duplicates are to be found.
*/
public void findDuplicate(int[] arr) {
HashMap map = new HashMap();
for (int i = 0; i < arr.length; i++) {
// first we check whether elements already exists in map or not
if (map.containsKey(arr[i])) {
// we do 2nd check to avoid printing the duplicate elements
// again every time we encounter the same element in array as we
// move forward.
if (map.get(arr[i]) == 0) {
System.out.println("Duplicate Element Found : " + arr[i]);
} else {
// we increment value to keep track of number of occurrence
// of that element.
int value = map.get(arr[i]);
value++;
map.put(arr[i], value);
}
} else {
// if element not present in hash map, put value in hash map
// with value 0.
map.put(arr[i], 0);
}
}
}
public static void main(String args[]) {
int arr[] = { 1, 2, 3, 4, 2, 1, 4, 5, 6, 7 };
new FindDuplicatesInArray().findDuplicate(arr);
}
}
During the program we are iterating through the array of size n. So the run time will be O(n). We also created a hash map to store the elements of array while iterating through it. Now in worst case all the elements of array are distinct, for which we will have to store the whole array in the hash map. This will require O(n) space time.
Solution 2: Run time : O(nlogn), space time: O(1).
This can be achieved by simply applying simple sorting and searching on given array. The following steps are involved for achieving the solution
i) Sort the given array by using a in place merge sort.
ii) Iterate through the array, if the next element of the array is same as current element, print the element as duplicate.
iii) skip all occurrence of the duplicate elements and continue step(ii).
The sorting of array is required to align all the duplicate elements together. We use merge sort as the best, average and worst run time of merge sort is nlogn. (For more info on merge sort and its implementation visit here).
While we iterate through the array, we check whether the next element is same as current element as in sorted array the duplicates will be in row. (Note: if the current element is last element of array, we don't need to check for next element).
Java Implementation:
import java.util.Arrays;
/*
* Program to find duplicate elements in an array.
*/
public class FindDuplicatesInArray {
/*
* Method to find duplicates in array.
*
* @param: Array for which the duplicates are to be found.
*/
public void findDuplicate(int[] arr) {
// By default java java collections have in-place merge sort
// as their generic sorting algorithm.
Arrays.sort(arr);
// we iterate through only 0 to (n - 1) to skip last element
// of array.
for (int i = 0; i < arr.length - 1; i++) {
if (arr[i] == arr[i + 1]) {
System.out.println("Duplicate element found: " + arr[i]);
// we skip all duplicate elements.
while (true) {
if (arr[i] == arr[i + 1] && i < arr.length - 1) {
i++;
}
else {
break;
}
}
}
}
}
public static void main(String args[]) {
int arr[] = { 1, 2, 3, 4, 2, 1, 4, 5, 6, 7 };
new FindDuplicatesInArray().findDuplicate(arr);
}
}
During the program, we are performing merge sort on the given array (For more info on merge sort and its implementation visit here). The run time for merge sort is O(nlogn). Also when we iterate through the array, we don't need extra space and run time for that is O(n). So total run time is : nlogn + n = nlogn. As we don't consume extra space the space time is constant. (i.e. O(1)).
2 comments:
Perfect!!
in first part , it does not go in else part. what is the use of that?
else {
// we increment value to keep track of number of occurrence
// of that element.
int value = map.get(arr[i]);
value++;
map.put(arr[i], value);
}
Post a Comment