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)){