Remove Element
Given an integer array arr[] and an integer X the task is to the remove all occurrences of X from arr[] in-place and return the number of elements which are not equal to X. If there are K number of elements which are not equal to X then the input array arr[] should be modified such that the first K elements should contain the elements which are not equal to X and then the remaining elements.
Note: The order of first K elements may be changed.
Examples:
Input: arr[] = {3, 2, 2, 3}, X = 3
Output: 2, arr[] = {2, 2, _, _}
Explanation: The answer is 2 because there are 2 elements which are not equal to 3 and arr[] will be modified such that the first 2 elements contain the elements which are not equal to 3 and remaining elements can contain any element.Input: arr[] = {0, 1, 3, 0, 2, 2, 4, 2}, X = 2
Output: 5, arr[] = {0, 1, 3, 0, 4, _, _, _}
Explanation: The answer is 5 because there are 5 elements which are not equal to 2 and arr[] will be modified such that the first 5 elements contain the elements which are not equal to 2 and remaining elements can contain any element.
Approach: To solve the problem, follow the below idea:
Use two pointers to the iterate through the array. One pointer, say i traverses every element of the array and another pointer, say j keeps track of the position of the elements that are not equal to X. When arr[i] is not equal to the X move it to the position indicated by j and increment j. The value of the j at the end of the process will be the count of the elements not equal to X.
Step-by-step algorithm:
- Initialize j to 0. This will track the count of the elements not equal to X.
- Iterate over each element in the array using the loop with the index i.
- If nums[i] is not equal to the X set nums[j] = nums[i] and increment j.
- Return j.
Here is the implementation of the above approach:
def removeElement(nums, val):
k = 0
# Initialize the counter for the elements not equal to the val
for i in range(len(nums)):
if nums[i] != val:
nums[k] = nums[i]
# Place the non-val element at the kth position
k += 1
# Increment the count of the non-val elements
return k
# Sample Input
nums = [0, 1, 3, 0, 2, 2, 4, 2]
val = 2
k = removeElement(nums, val)
print(k)
print(nums[:k])
Output
5 [0, 1, 3, 0, 4]
Time Complexity: O(N), where N is the number of elements in arr[]
Auxiliary Space: O(1)
Contact Us