Table of contents
Overview
Removing array elements is by far one of the most important requirements in many software and real-life applications ranging from information gathering, and research analysis to AI/ML and IoT applications. In this coding challenge put together I4G, I will be looking at how I come to implement element removal a using the C++ programming language.
Thought Process
The main task in this challenge is to remove elements from arrays e.g 1, 2, 3, 3, 4, 5, 6, 7 ...
Looking at this from a Linear Search algorithm perspective, we are basically going through each element of the array and checking if an element says element k is the same as the said element say k. We, therefore, remove the element from the array.
In the case of this task where no extra memory is to be allocated, a simple approach is to use a placeholder variable to keep track of the array elements, this just inserts the array element that is not the same as the element we want to remove into the next array element meaning it overwrites whatever is already at that position. For example say we have an array [ 2, 2, 3, 4, 5, 5, 6], we loop through the elements of this array and whenever we encounter the element we do not want to remove, we simply insert it into our placeholder position.
if(an array is not equal to the value){
insert an element into the placeholder position
}
Conclusion
With this implementation, memory is saved and we have a fast run time.
Time complexity: O(n). Both i and n traverse at most n steps. In this approach, the number of assignment operations is equal to the number of elements to remove. So it is more efficient if elements to remove are rare.
Space complexity: O(1).
Acknowledgement I4G10DaysOfCodeChallenge