# C Solution (O(n) and no additional space)

• ``````int* findDisappearedNumbers(int* nums, int numsSize, int* returnSize) {
int* histogram = (int*) malloc(sizeof(int) * (numsSize + 1));
memset(histogram, 0, sizeof(int) * numsSize);

for (int index = 0; index < numsSize; index++) {
histogram[nums[index]]++;
}

histogram[0] = 1;
for (int index = 1; index <= numsSize; index++) {
if (histogram[index] == 0) {
histogram[histogram[0]] = index;
histogram[0]++;
}
}
*returnSize = histogram[0] - 1;
return &histogram[1];
}
``````

Keeping a histogram array, and later traversing the histogram to return elements with 0 values allows us to solve this problem with O(n) complexity. Index 0 of the histogram was used to store the number of missing numbers.

• a perfect solution!

• Your solution works fine when the array is in small size. Suppose the array size is 10^6, and only has one disappeared number. Your solution will allocate 4*10^6 bytes to hold data. But actually you only need 4 bytes.

• you malloc first, in my opinion, that's the addtional space the author means.

• ``````/**
* Return an array of size *returnSize.
* Note: The returned array must be malloced, assume caller calls free().
*/
``````

According to the requirements, caller calls free(). The returned pointer in this case to &histogram[1] is not a valid pointer to be freed.

Instead of using histogram[0] as the counter, can use (*returnSize) instead, allowing the return array to start at histogram[0] and can simply `return histogram`;.

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