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++.