Remove all occurrences of an element from an array

© Parineeth M R

Question 19. Given an array, remove all occurrences of an element from the array


Suppose the given array is A = {1, 4, 2, 1, 5, 2} and we have to remove all occurences of 1 from it, then the result array is {4, 2, 5, 2}. The element to be removed from the array can be present in multiple locations. We can efficiently remove all occurrences of the element in O(1) space and O(n) time in a single pass through the array by doing the following:

1. Maintain a variable called fill_pos to keep track of where we should store the next element of the array that should not be deleted. Initialize fill_pos to 0.

2. Traverse through the array. If the current element in the array should be deleted then skip it. If current element in the array should not be deleted, then store the current element at fill_pos in the array and increment fill_pos

C/C++


/*
a: input array from which all occurrences of an element should be removed
length: number of elements in array a 
x: element to be removed
Return value: number of elements in a after removing x 
*/
int remove_element(int a[], int length, int x)
{
	int i, fill_pos;

	fill_pos = 0;
	for (i = 0; i < length; ++i) {
		if (a[i] != x) {
			a[fill_pos] = a[i];
			fill_pos++;
		}
	}

	return fill_pos;
}



Java


/*
a: input array from which all occurrences of an element should be removed
x: element to be removed
Return value: output array after removing x 
*/
public static int[] removeElement(int[] a, int x) {
	int fillPos = 0;
	for (int i = 0; i < a.length; ++i) {
		if (a[i] != x) {
			a[fillPos] = a[i];
			fillPos++;
		}
	}

	int[] result = Arrays.copyOf(a, fillPos);
	return result;
}



Python


#a: input list from which all occurrences of an element should be removed
#x: element to be removed
def remove_element(a, x) :
	length = len(a)
	fill_pos = 0
	for  i in range(0, length):
		if (a[i] != x) :
			a[fill_pos] = a[i]
			fill_pos += 1
	
	#delete all the elements from fill_pos onwards	
	if (fill_pos < length) :
		del a[fill_pos:]