How to achieve 0ms with C?

• My O(n) solution takes 4ms. But there seems to be some 0ms submissions?

• calling malloc 60 (current number of test cases) times will for sure by itself take over 1ms on a reasonable machine. My guess is that 0ms were achieved in the past with fewer test cases.

I have a 3ms solution that uses ghetto hash table/set sorta thing:

``````#define HASH_SIZE 4096
int hash(int val) {
return val%HASH_SIZE;
}

void insert(int val, int *set, int *visited, int *order, int *size) {
int h = hash(val);
while(visited[h] && set[h]!=val)
h = (h+1)%HASH_SIZE;
if (!visited[h]) {
order[*size] = val;
(*size)++;
set[h] = val;
visited[h] = 1;
}
}

bool inSet(int val, int *set, int *visited) {
int h = hash(val);
while(visited[h] && set[h]!=val)
h = (h+1)%HASH_SIZE;
return visited[h];
}

/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
int* intersection(int* nums1, int nums1Size, int* nums2, int nums2Size, int* returnSize) {
int nums1Set[HASH_SIZE];
int visited1[HASH_SIZE]={0};

int nums2Set[HASH_SIZE];
int visited2[HASH_SIZE]={0};
int order2[HASH_SIZE];

for(int i=0; i<nums1Size; i++)
insert(nums1[i], nums1Set, visited1, order2, returnSize);

*returnSize=0;
for(int i=0; i<nums2Size; i++)
if(inSet(nums2[i], nums1Set, visited1))
insert(nums2[i], nums2Set, visited2, order2, returnSize);

int *ret = (int *)malloc(sizeof(int)*(*returnSize));
for(int i=0; i<*returnSize; i++)
ret[i]=order2[i];

return ret;
}``````

Looks like your connection to LeetCode Discuss was lost, please wait while we try to reconnect.