Below is easy level problem it seems:
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.
In Python, if we are writing using hash list or dictionary , its simple. Time complexity will be O(n) and space complexity will be O(n). But one thing I dont understand how the dictionary search happens in Python internally. Does it not use a loop . Please provide your comments.
But if we have to write in C language, simple way is to write in 2 for loops where the time complexity is O(n*n) and space complexity is O(1).
But if we want to write with time complexity of O(n) similar to Python, hash table not possible in my perspective. Why not possible : integer in array can be of any integer value, integer can be 2**31 also. If we need to do hashmap of that integer then hash table should be such big to hold that index value. Can we implement this in C using hash table. Please provide your comments with O(n) time complexity.
Finally I could use merge sort knowledge to implement this. Below is my code: I added prints in comments. these prints may be helpful to understand the functionality.
bool Check4Dup(int* nums, int start, int end);
bool containsDuplicate(int* nums, int numsSize){
int start =0, end= numsSize-1;
return Check4Dup(nums, start, end);
}
bool MergeNcheck(int* nums, int start, int mid, int end)
{
int ii = start, jj=mid+1;
int temp[end-start+1],ind=0;
// printf(“%d line, start %d, mid %d, end %d, num[%d] %d, num[%d] %d , num[%d] %d\n”,
// __LINE__,ii, mid, end, start, nums[start], mid, nums[mid], end, nums[end]);
while (ii<=mid && jj<=end)
{
// printf(“%d line nums[%d] %d, nums[%d] %d\n”,
// __LINE__, ii,nums[ii],jj, nums[jj]);
if (nums[ii] == nums[jj])
return 1;
if (nums[ii]< nums[jj])
temp[ind++] = nums[ii++];
else
temp[ind++] = nums[jj++];
}
while (ii<=mid)
{
temp[ind++] = nums[ii++];
}
while (jj<=end)
{
temp[ind++] = nums[jj++];
}
for (ii=start;ii<=end;ii++)
{
nums[ii]=temp[ii-start];
//printf(“%d line, start %d, end %d, nums[%d] %d\n”,
// __LINE__,start, end, ii, nums[ii]);
}
return 0;
}
bool Check4Dup(int* nums, int start, int end)
{
int mid = (start+end)/2;
bool res = 0;
// printf(“%d line, start %d, end %d\n”, __LINE__,start, end);
if (start < end)
{
//printf(“%d line, start %d, end %d, mid %d, “)
if ((mid != start) && (nums[mid] == nums[start]))
return 1;
if ((mid != end) && (nums[mid] == nums[end]))
return 1;
res = Check4Dup(nums, start, mid);
if (!res)
res = Check4Dup(nums, mid+1, end);
// printf(“%d line, start %d, end %d, mid %d\n”, __LINE__,start, end, mid);
if (!res)
res = MergeNcheck(nums,start, mid, end);
}
return res;
}
