C LeetCode Problem and Solution — Check if an array contains duplicate elements
--
C LeetCode problem and solution — Check if an array contains duplicate elements
Given an integer array nums, return true if any value appears at least twice in the array, and return false if every element is distinct. I provide two possible solutions in C, one is brute force and O(N²) while the second one is O(nlogn).
Example 1:
Input: nums = [1,2,3,1]
Output: true
Example 2:
Input: nums = [1,2,3,4]
Output: false
Example 3:
Input: nums = [1,1,1,3,3,4,3,2,4,2]
Output: true
My solution is quite intuitive and it runs in O(N²) time. The worst case is where there are no duplicates, as both loops will have to execute till the end. Best case is if there are duplicate entries in the beginning as the program will detect tat and return true without needing to traverse so far.
bool containsDuplicate(int* nums, int numsSize){
for(int i = 0; i < numsSize; i++){ //outer loop n
for(int j = 0; j < i; j++){ //inner loop n
if(*(nums+j) == *(nums+i)){
return true; //found match
}
}
}
return false;
}
As it is brute force, we are better off with a different approach. Unsurprisingly, this will not run in LeetCode because it just takes too much time ;)
One possible approach would be to start sorting the array, then check for duplicates as they would have to appear in consecutive order. QuickSort, is the sort I selected is included in the C library. Unfortunately, the efficiency isn’t defined from the C standard, but we can assume it works similar to/ if not better than a standard quick sort.
It should be somewhere around O(nlogn) in the best and average case, while the worst is unknown as we don’t know where the partition is… It is certainly going to be better than O(N²). Just a reminder about the worst case in a standard QuickSort…
