 |
The problem statement : https://leetcode.com/problems/contains-duplicate/
The simplest and naive implementation of this question is to iterate through all elements and compare with the other to check if array contains duplicate or not.
It would look something like this :
bool bruteForceSolution(int* a, int size){ //you could pass a vector as well
for (int i = 0; i < size; i++){
for (int j = 0; j < size; j++){
if(i != j && a[i] == a[j]){
return true;
}
}
}
return false;
}
This solution will not only iterate through all elements of an array till the last in the worst case but also have an inner loop that will double the amount of elements to iterate through which is why it is an inefficient solution. It will cause big O(n)2 where n is the number of elements and since we have inner loop as well, n2 is the runtime complexity.
Another approach to solve this is using map and set. I am using c++ language but pretty much every language would have those data structures available for you to use. This is an efficient solution because it has big O(n) runtime complexity because we will be iterating through elements only once in the worst case.
bool usingSet(int* a, int size) {
unordered_set<int> mSet;
for (int i = 0; i < size; i++){
if(mSet.count(a[i])) // count returns 1 if element exists, 0 otherwise.
return true;
mSet.insert(a[i]);
}
return false;
}
bool usingMap(int *a, int size){
unordered_map<int, int> map;
for (int i = 0; i < size; i++){
if(map.find(a[i]) != map.end()){ // Checking if find didn't reach till end, means element found.
return true;
}else{
map[a[i]]++;
}
}
return false;
}
Documentation for unordered_set - https://cplusplus.com/reference/unordered_set/unordered_set/
Documentation for unordered_map - https://cplusplus.com/reference/unordered_map/unordered_map/
Full source code of C++ solution using map, set and brute force -> https://github.com/apprajapati9/CPlusPlus/blob/master/C%2B%2B/Leetcode/contains-duplicate/contains-duplicate.cpp
0 Comments