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

  • 5
    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[0] = 1;
        for (int index = 1; index <= numsSize; index++) {
            if (histogram[index] == 0) {
                histogram[histogram[0]] = index;
        *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.

  • 0

    a perfect solution!

  • 0

    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.

  • 0

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

  • 0
     * 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;.

Log in to reply

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