Remove elements from a given array

Question

I am doing an problem on Leetcode. The question is that given an array and a value, remove all instances of that value in place and return the new length. Or you can read it here:

int removeElement(int* nums, int numsSize, int val) {
    int *nums_copy; 
    int count = 0;
    int actual_count = 0;


    while (actual_count < numsSize) {

        if (nums[actual_count] != val) {
            nums_copy[count] = nums[actual_count];
            count++;
            nums_copy = realloc(nums_copy, sizeof(int)* count);
        } 
        actual_count++;
    }

    nums = nums_copy;
    return actual_count;
}

When I tried to test it with [1, 2, 2, 3], 2, the output is [1, 2, 2, 3] while the expected output is [1, 3].

WHy don't you click [Discuss](https://leetcode.com/discuss/questions/oj/remove-element) and see how other people solve the problem? — Dylan Czenski, Jan 08 '16 at 02:13

score 1 · Answer 1 · answered Jan 07 '16 at 22:15

Firstly, you don't need to realloc, the problem says to remove the value in place. Secondly, what you need to do is to simply walk through the array and shift it one position to the left when you encounter the searched value. And decrement the resulted count.

score 0 · Answer 2 · edited May 23 '17 at 12:15

0

Apparently, you have not specified how much memory you want to allocate after int *nums_copy. Use malloc from stdlib to allocate variable amount of memory on heap, or alloca to allocate on stack, but bear this in mind.

edited May 23 '17 at 12:15

Community

1
1

answered Jan 07 '16 at 22:13

theoden8

773
7
16

score 0 · Accepted Answer · answered Jan 08 '16 at 00:45

The problem does not need to memory allocation. All that is needed is to have the matching elements towards the end of the list. Here is an example.

array = 3, 2, 5, 2, 7, 2
len = 6
val = 2

We want to achieve something like

array = 3, 7, 5, 2, 2, 2
newlength = 3

SOLUTION One approach is the following

Repeat:

Start with two marker (either index or pointer) one pointing to the leftmost and one pointing to the rightmost element

3, 2, 5, 2, 7, 2
L              R

Move the left marker to the right if it matches to 'val'. Do it until the matching stops or it reaches the right marker.

3, 2, 5, 2, 7, 2
   L           R

(Opposite for right marker.) Move the right marker to the left if it matches to 'val'. Do it until the matching stops or it reaches the left marker.

3, 2, 5, 2, 7, 2
   L        R

Swap the elements corresponding to the left and right markers.

3, 7, 5, 2, 2, 2
   L        R

Go to Repeat.

Celine NOEL · Answer 4 · 2016-01-08T00:24:55.747

Here this should work:

int removeElement(int* nums, int numsSize, int val) {
    int countNums = 0;
    int countCpy = 0;

    while (countNums < numsSize) {
        if (nums[countNums] != val) {
            // Copy the number.
            nums[countCpy] = nums[countNums];
            ++ countCpy;
        } 

        ++ countNums;
    }

    return countCpy;
}

As for why this output you got was [1, 2, 2, 3], I don't really understand. As you're trying to set nums_copy[0] before having allocated nums_copy, you should be getting a segfault. I suppose it's due to the platform you're coding on.

Dylan Czenski · Answer 5 · 2016-01-08T01:11:26.050

-1

The given code uses std::vector, so why not use its build-in functions?

int removeElement(vector<int>& nums,int val){

    vector<int> newNums();  

        for (int i=0; i<nums.size(); i++){
            if (nums[i]!=val){
                newNums.push_back(nums[i]);
            }
        }

    return newNums.size();
}

edited Jan 08 '16 at 01:11

answered Jan 08 '16 at 00:52

Dylan Czenski

1,305
4
29
49

score -1 · Answer 6 · answered Jan 08 '16 at 06:50

int removeElement(int* nums, int numsSize, int val) {

    int i, j;

    for(i = 0, j = 0 ; i < numsSize ; i++){
        if( nums[i] == val ) continue;
        nums[ j ] = nums[ i ];              // blind copy
        j++;
    }
    /*
        nums = realloc( nums, j * sizeof( int ) );
    */
    return j;   //actual_count
}

Remove elements from a given array

6 Answers6