I saw a interview question as follows:
One number in array is duplicating.Find it
Simple solution is as follows:
for(int i=0;i<n;i++){
{
dup = false;
for(j=0;j<n;j++){
if(i!=j && a[i]= a[j]){
dup = true;
}
if(dup == true)
return a[i]
}
}
But I want to implement it in O(n log(n)) and in O(n) time. How can i do it?
Sort the array (that can be done in the first O (n Log n) then the comparison just has to be done for the adjacent elements. Or just put the array into a hash table and stop if you find the first key with an exsting entry.
I'm answering to "Finding duplicate element in an array?"
You search for i and j from 0 to < n, and later you check for j != i. Instead you could form your loops like this:
for (int i=0; i<n-1; i++)
{
for (j=i+1; j<n; j++)
{
if (a[i] == a[j])
{
return i;
}
}
}
return -1;
Repeatedly setting dup=false is nonsense. Either dup is still false, or it was true, then you left the code with 'return'.
Writing the previous answers in actual code (Java):
O(n log n) time:
Arrays.sort(arr);
for (int i = 1; i < arr.length; i++)
if (arr[i] == arr[i - 1])
return arr[i];
throw new Exception(); // error: no duplicate
O(n) time:
Set<Integer> set = new HashSet<Integer>();
for (int i = 0; i < arr.length; i++) {
if (set.contains(arr[i]))
return arr[i];
set.add(arr[i]);
}
throw new Exception(); // error: no duplicate
Set<Integer> set = new HashSet<>(arr.length); (if probability of a duplicate close to the start is low - if it is high, you're better off with a tree implementation of Set). Use foreach loop. Just add the element and return if !Set.add(arr[i]).I recommend to use the hash-map (assuming no collisions) to solve it.
private boolean hasDuplicate(int[] arr) {
Map<Integer, Boolean> map = new HashMap();
// find the duplicate element from an array using map
for (int i = 0; i < arr.length; i++) {
if(map.containsKey(arr[i])) {
return true;
} else {
map.put(arr[i], true);
}
}
return false;
}
Time complexity : O(n)
Space complexity : O(n)
Another approach is sorting and comparing and but the sorting adds extra overhead.
By using collections we can go for below code snippet -
Set<String> set = new HashSet<String>();
for (String arrayElement : arr) {
if (!set.add(arrayElement)) {
System.out.println("Duplicate Element is : " + arrayElement);
}
}
Find O(n) complexity solution as below -
int ar[]={0,1,2,3,0,2,3,1,0,2};
Set <Integer>mySet=new HashSet<>();
for(int n:ar){
if(!mySet.add(n)){
System.out.println(" "+n);
}
}
And another process with lesser space complexity O(N) and possibly O(n Log n) --
public void duplicateElementSolution(int ar[]){
Arrays.sort(ar);
for(int i=0;i<(ar.length-1);i++){
if(ar[i]==ar[i+1]){
System.out.println(" "+ar[i]);
}
}
}
var containsDuplicate = function(nums) {
const set = new Set();
for (const num of nums) {
if (set.has(num)) {
return true; // Found a duplicate
}
set.add(num);
}
return false; // No duplicates found
};
var when you know you have const? Why?(The question in its current form is a little confusing - my answer is assuming that the question is about finding two numbers in an array that sum to a given value)
Since the given array is unsorted, I am assuming that we are not allowed to sort the array (i.e. the given order of the array cannot be changed).
The simplest solution IMHO is to iterate over each number x and check if I-x occurs anywhere in the arrays. This is essentially what your O(n^2) solution is doing.
This can be brought down to O(n) or O(nlogn) by making the search faster using some sort of fast set data structure. Basically, as we iterate over the array, we query to see if I-x occurs in the set.
Code (in Python):
l=[1,2,3,4,5,6,7,8,9]
seen=set()
I=11
for item in l:
if I-item in seen:
print "(%d,%d)"%(item,I-item)
seen.add(item)
The complexity of the solution depends on the insert/lookup complexity of the set data structure that you use. A hashtable based implementation has a O(1) complexity so it gives you a O(n) algorithm, while a tree based set results in a O(nlogn) algorithm.
Edit:
The equivalent data structure to Python's set would be stl::set in C++ and TreeSet/HashSet in Java. The line I-x in seen would translate to seen.contains(I-x) in Java and seen.find(I-x)==seen.end() in C++.
I=item in seen).
Reference java.util.TreeSet which is implemented Red-Black tree underlying, it's O(n*log(n)).
