This is one of basic searching algorithm question.
In this post, we'll look into different approaches of checking whether array has duplicate elements or not. In addition to this, we'll also see how to find all duplicate elements from array in one pass.
Approach 1 Brute-Force approach
In this method, for each input elements check whether there is any element with the same value. This we can solve with two loops.
Time Complexity : O(n^2) for nested loops, Space Complexity : O(1)
Approach 2 In this approach, we first sort the array using merge or heap sort which give O(nlogn) complexity. Then with another scan on this sorted array, we check if there are elements with same value and adjacent.
Time Complexity : O(nlogn) for sorting, Space Complexity : O(1)
Approach 3 We can improve the complexity of above approach using HashMap. In this method, we create a Hash map and enter the key as array element and value as counter 1 which indicate the element is already occurred.
Time Complexity : O(n), Space Complexity : O(n)
Approach 4 In this approach we assume that all the element are positive integer and element are in the range of 0 to n-1 otherwise it will give exception.
For each element A[i], go to array element element whose index is A[i] i.e, for each index we get the value which correspond to the index means A[A[i]. We negate this value. While iterating we check whether A[A[i] is already negative or not, if yes it means this is the duplicate element.
Array containing 0 element may not give result because we can't make 0 -ve.
Time Complexity : O(n) since only one scan is required, Space Complexity : O(1)
Approach 5 In this method, we'll try to find out all the duplicate elements which are present in the array. This is modification of approach 4.
Approach 6 Using Java Set
This approach is better than 4 & 5 because there is not assumption here about array.
Set is a collection that contains no duplicate elements and it doesn't allow insertion of duplicate elements we can check the same while inserting into set.
If you know anyone who has started learning Java, why not help them out! Just share this post with them.
Thanks for studying today!...
In this post, we'll look into different approaches of checking whether array has duplicate elements or not. In addition to this, we'll also see how to find all duplicate elements from array in one pass.
Approach 1 Brute-Force approach
In this method, for each input elements check whether there is any element with the same value. This we can solve with two loops.
Approach 2 In this approach, we first sort the array using merge or heap sort which give O(nlogn) complexity. Then with another scan on this sorted array, we check if there are elements with same value and adjacent.
Approach 3 We can improve the complexity of above approach using HashMap. In this method, we create a Hash map and enter the key as array element and value as counter 1 which indicate the element is already occurred.
Approach 4 In this approach we assume that all the element are positive integer and element are in the range of 0 to n-1 otherwise it will give exception.
For each element A[i], go to array element element whose index is A[i] i.e, for each index we get the value which correspond to the index means A[A[i]. We negate this value. While iterating we check whether A[A[i] is already negative or not, if yes it means this is the duplicate element.
Array containing 0 element may not give result because we can't make 0 -ve.
Time Complexity : O(n) since only one scan is required, Space Complexity : O(1)
Approach 5 In this method, we'll try to find out all the duplicate elements which are present in the array. This is modification of approach 4.
This approach is better than 4 & 5 because there is not assumption here about array.
Set is a collection that contains no duplicate elements and it doesn't allow insertion of duplicate elements we can check the same while inserting into set.
If you know anyone who has started learning Java, why not help them out! Just share this post with them.
Thanks for studying today!...
Pradeep kumar In approach 5 to find duplicate values i found these cases are not working as expected based on ur code,
ReplyDeleteint A[]=new int[]{6,7,5,4,3,2}; //When no duplicates, it showing as "array out of bounds expection"
int A[]=new int[]{6,7,5,4,3,2,1,0,7}; //When 1,0 is given in array before 2nd duplicate value, it is not showing any duplicate values even '7' is duplicated
{6,7,5,4,3,2} ; this is not in the range as per assumption of approach 4.
Delete6,7,5,4,3,2,1,0,7} : this not as per assumption of positive number because we can't make 0 -ve that why it will not give expected result
Hi,
ReplyDeleteApproach 2 will give indexoutofbounds exception when there are no duplicates
Right, Loop should work till A.length-1
Delete"I very much enjoyed this article.Nice article thanks for given this information. i hope it useful to many pepole.php jobs in hyderabad.
ReplyDelete"