Runtime error : Heap Buffer overflow in Leet code

Question

I am having a problem with this code on Leetcode. In there , I am solving a problem to remove duplicates in an array but I am getting heap buffer overflow error -

Here's the code -

int removeDuplicates(int* nums, int numsSize) {

    int i,j,temp,k=0,num = *(nums+numsSize-1);

    for(i = 0;i<numsSize;i++){
        
        if(*(nums+i) == *(nums+i+1)){


            if(num != *(nums+i)){
                k++;
            }
        
            for(j = i+1;j<numsSize;j++){
                temp = *(nums+j);
                *(nums+j) = *(nums+j+1);
                *(nums+j+1) = temp; 

            }
            num = *(nums+i);
            i--;

        }
    }
    return k;
    
}

I want to know what causing this error and how to solve it?

Answer 1

First of all, for the sake of readability get rid of all access in the form of *(nums+i) and replace it with nums[i].

At the last iteration of the loop, if(*(nums+i) == *(nums+i+1)){ will overflow, because nums+i+1 is then equivalent to nums + numsSize-1 + 1 which is one item out of bounds.

You can solve this by for example doing for(i = 1; i<numsSize; i++){ and then if(nums[i-1] == nums[i]).

Same issue with *(nums+j+1);.

Answer 2

It seems the task is either to remove duplicates from a sorted array or to remove adjacent duplicated elements in any array.

First of all the function should be declared like

size_t removeDuplicates(int* nums, size_t numsSize);

that is the type of its second parameter and the return type should be the unsigned integer type size_t instead of the signed integer type int. Leet code does not learn how to write professional code.

Your code has bugs, a logical error and is inefficient.

This line

int i,j,temp,k=0,num = *(nums+numsSize-1);

is already wrong. The user may pass any value for the parameter numsSize as for instance 0. In this case the expression *(nums+numsSize-1) invokes undefined behavior.

Or for example if a passed array has no duplicates then your function returns k equal to 0 due to skipping this if statement

    if(*(nums+i) == *(nums+i+1)){


        if(num != *(nums+i)){
            k++;
        }
        //...

(where in the nested if statement the variable k is incremented) instead of returning the actual number of unique elements.

Or consider for example an array like { 1, 1, 1 } where all elements are equal each other. In this case num will be always equal to *(nums+i). So the returned value of k again will be equal to 0 while you have to return 1.

The function is inefficient due to this for loop

        for(j = i+1;j<numsSize;j++){
            temp = *(nums+j);
            *(nums+j) = *(nums+j+1);
            *(nums+j+1) = temp; 

        }

where for some iterations of the outer for loop all elements of a sub-array of the original array are moved left.

And the function contains bugs due to accessing memory outside the array when i in the outer for loop or j in the inner for loop are equal to numsSize - 1 because expressions i+1 and j+1 are equal to numsSize while the valid range of indices for the array is [0, numsSize).

I would define the function the following way as shown in the demonstration program below.

#include <stdio.h>

size_t removeDuplicates( int a[], size_t n )
{
    size_t unique = 0;

    if (n)
    {
        for (size_t i = 1; i < n; i++)
        {
            if (a[unique] != a[i])
            {
                if (i != ++unique)
                {
                    a[unique] = a[i];
                }
            }
        }

        ++unique;
    }

    return unique;
}

int main( void )
{
    int a[] = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };

    size_t unique = removeDuplicates( a, sizeof( a ) / sizeof( *a ) );

    for (size_t i = 0; i < unique; i++)
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );
}

The program output is

1 2 3 4 5

If you want to reformat a sorted array such a way that all values stored in the array were kept and duplicated elements were moved to the tail of the array then there are two possibilities: whether the moved elements will be stored in the sorted order or in the reversed sorted order.

Here are another two demomnstration programs.

In the first program the function moves duplicated elements to the tail of an array in the reversed sorted order.

#include <stdio.h>
#include <string.h>

size_t removeDuplicates( int a[], size_t n )
{
    size_t unique = 0;

    if (n)
    {
        for (size_t i = 1; i < n; )
        {
            if (a[unique] != a[i])
            {
                if (i != ++unique)
                {
                    a[unique] = a[i];
                }
                ++i;
            }
            else
            {
                int tmp = a[i];
                memmove( a + i, a + i + 1, ( n - i - 1 ) * sizeof( int ) );
                a[--n] = tmp;
            }
        }

        ++unique;
    }

    return unique;
}

int main( void )
{
    int a[] = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };
    size_t n = sizeof( a ) / sizeof( *a );

    size_t unique = removeDuplicates( a, n );

    for (size_t i = 0; i < n; i++)
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );

    for (size_t i = 0; i < unique; i++)
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );
}

The program output is

1 2 3 4 5 5 5 5 5 4 4 4 3 3 2
1 2 3 4 5

In the second program the function moves duplicated elements to the tail of an array in the initial sorted order.

#include <stdio.h>
#include <string.h>

size_t removeDuplicates( int a[], size_t n )
{
    size_t unique = 0;

    if (n)
    {
        for (size_t i = 1, m = n; i < m; )
        {
            if (a[unique] != a[i])
            {
                if (i != ++unique)
                {
                    a[unique] = a[i];
                }
                ++i;
            }
            else
            {
                int tmp = a[i];
                memmove( a + i, a + i + 1, ( n - i - 1 ) * sizeof( int ) );
                a[n - 1] = tmp;
                --m;
            }
        }

        ++unique;
    }

    return unique;
}

int main( void )
{
    int a[] = { 1, 2, 2, 3, 3, 3, 4, 4, 4, 4, 5, 5, 5, 5, 5 };
    size_t n = sizeof( a ) / sizeof( *a );

    size_t unique = removeDuplicates( a, n );

    for (size_t i = 0; i < n; i++)
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );

    for (size_t i = 0; i < unique; i++)
    {
        printf( "%d ", a[i] );
    }
    putchar( '\n' );
}

The program output is

1 2 3 4 5 2 3 3 4 4 4 5 5 5 5
1 2 3 4 5

As you can see in the both cases all stored values in arrays are preserved without changes.