No. 32 - Remove Numbers in Array

Question: Given an array and a value, how to implement a function to remove all instances of that value in place and return the new length? The order of elements can be changed. It doesn't matter what you leave beyond the new length.

For example, if the input array is {4, 3, 2, 1, 2, 3, 6}, the result array after removing value 2 contains numbers {4, 3, 1, 3, 6}, and the new length of the remaining array is 5.

Analysis: The most straightforward solution for this problem is to scan the whole array from the beginning to end. When a target number is scanned, remove it and move all number behind it backward. The overall complexity is O(n²), since we have to move O(n) numbers when a target value is removed.

We can notice that it is not required to keep the order for the remaining numbers, and it does not care what numbers left beyond the new length. Therefore, we can move all target numbers to be removed to the end of the array.

Two pointers are defined to solve this problem: The first pointer (denoted as p1) moves forward until it reaches a number equal to the target value, which is initialized to the beginning of array. The other (denoted as p2) moves backward until it reaches a number not equal to the target value, which is initialized to the end of array. Two numbers pointed by p1 and p2 are swapped. We repeat the moving and swapping operations until all target numbers are scanned.

The sample code is shown as below:

unsigned int Remove(int* numbers, unsigned int length, int n)

{

    if(numbers == NULL || length < 1)

        return 0;

    int* p1 = numbers;

    int* p2 = numbers + length - 1;

    while(p1 < p2)

    {

        while(*p1 != n && (p1 - numbers) < length)

            ++p1;

        while(*p2 == n && (p2 - numbers) > 0)

            --p2;

        if(p1 < p2)

        {

            *p1 = *p2;

            *p2 = n;

        }

    }

    return p1 - numbers;

}

Because p1 points to the first target number in the array after scanning and swap, all elements at the left side of p2 are the remaining numbers. The new length can be calculated by the difference between the beginning of array and p1.

Since it is only required to scan the whole array once, and it costs O(1) time to swap a target value to the end of array, the overall time complexity is O(n) for an array with n numbers.

The discussion about this problem is included in my book <Coding Interviews: Questions, Analysis & Solutions>, with some revisions. You may find the details of this book on Amazon.com, or Apress.
 

The author Harry He owns all the rights of this post. If you are going to use part of or the whole of this ariticle in your blog or webpages,  please add a reference to http://codercareer.blogspot.com/. If you are going to use it in your books, please contact him via zhedahht@gmail.com . Thanks.