Given an array of arbitrary numbers and a given value, how do we write a program to delete all instances of the given value?
For example, if the input array is [23, 9, 18, 9, 6, 47, 3, 6] and the element to be deleted is 9. The result array should be [23, 18, 6, 47, 3, 6]. Result array size is 6. We don’t care about the elements beyond this size.
The restriction is to modify the input array itself (should not use extra memory – constant extra space) and return the new length of the result array.
This problem can be solved as follows.
We maintain two indices; one to track the elements of resultant array (result index), and another to iterate through all the elements. While iterating through each element using second index, if we see an element which is not equal to the target element, we can copy it to the same array from the beginning, and increment the result index.
We maintain two indices; one to track the elements of resultant array (result index), and another to iterate through all the elements. While iterating through each element using second index, if we see an element which is not equal to the target element, we can copy it to the same array from the beginning, and increment the result index.
This algorithm runs in O(n) time and O(1) space complexity.
Here is the simple implementation in C++.
This file contains bidirectional Unicode text that may be interpreted or compiled differently than what appears below. To review, open the file in an editor that reveals hidden Unicode characters.
Learn more about bidirectional Unicode characters
#include <iostream> | |
using namespace std; | |
int removeElement(int A[], int n, int elem) | |
{ | |
int res = 0; | |
for( int i = 0; i < n ; i++ ) | |
{ | |
if( A[i] != elem ) | |
A[res++] = A[i]; | |
} | |
return res; | |
} | |
int main() | |
{ | |
int A[] = {10, 13, 9, 6, 13, 8, 5, 42, 24, 36}; | |
int size = removeElement( A, 10, 13);//delete 13 from the array | |
for( int i = 0 ; i < size; i++ ) | |
cout << A[i] << " "; | |
return 0; | |
} |