Remove Element
Given an integer array nums
and an integer val
, remove all occurrences
of val
in nums
inplace. The relative order of the elements may be changed.
Since it is impossible to change the length of the array in some languages, you must instead have the result be placed in the first part of the array nums
. More formally, if there are k
elements after removing the duplicates, then the
first k
elements of nums
should hold the final result. It does not matter what you leave beyond the
first k
elements.
Return k
after placing the final result in the first k
slots of nums
.
Do not allocate extra space for another array. You must do this by modifying the input array inplace with O(1) extra memory.
date this, nums1
has a length of m + n
, where the first m
elements denote the
elements that should be merged, and the last n
elements are set to 0
and should be
ignored. nums2
has a length of n
.
Problem Statement
The problem is to write a function that takes an integer array
nums
and an integer val
as inputs, and removes all occurrences of val
from nums
inplace,
without using any extra memory. The relative order of the remaining elements in the array may be changed, but we need to maintain the order of the
elements that are not removed.
The function should return an integer k
, which represents the number of elements remaining in the modified array. The first
k
elements of the nums
array should hold the final result, and it does not matter what we leave beyond the first
k
elements.
In other words, the function should modify the input array
nums
inplace such that it contains only the elements that are not equal to val
, and return the number of such elements.
Examples
Example 1:
Input: nums = [3,2,2,3], val = 3 Output: 2, nums = [2,2,_,_] Explanation: Your function should return k = 2, with the first two elements of nums being 2. It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2 Output: 5, nums = [0,1,4,0,3,_,_,_] Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4. Note that the five elements can be returned in any order. It does not matter what you leave beyond the returned k (hence they are underscores).
Clarifying Questions
 Can you please confirm that the input array is an integer array?
 Can you provide an example input and output for this problem?
 When you say "remove all occurrences of val", do you mean that all instances of val should be removed from the array or only the first instance of val should be removed?
 Can the input array contain duplicate elements other than the value to be removed?
 When you say "the relative order of the elements may be changed", can you provide an example of how the order of elements could be changed?
 Do we need to maintain the original order of the elements in the array, except for the elements we remove?
 Can we assume that the input array is nonempty, or do we need to handle empty input arrays as well?
Solutions
There are several approaches to solving this problem. Here are a few possible ones:

Brute Force

Twopointers approach

Using builtin functions

Using a stack

Using recursion
Brute Force:
We can iterate through the array and remove each occurrence of
val
by shifting all the subsequent elements one position to the left. This approach has a time complexity of O(n^2) and requires O(1)
extra memory.
Algorithm:
 Initialize a variable
count
to 0. 
Iterate through the array from left to right:
 If the current element is equal to
val
, remove it and shift all subsequent elements one position to the left.  Otherwise, increment
count
.
 If the current element is equal to
 Return
count
.
Time Complexity:
 The algorithm traverses the entire input array once, performing a constant amount of work at each iteration, except when deleting elements from the list in the Python implementation.
 In the worst case, all elements of the input array are equal to the value to remove, so the algorithm will traverse the entire input array and perform a constant amount of work at each iteration, resulting in a time complexity of O(n).
 In the best case, none of the elements of the input array are equal to the value to remove, so the algorithm will traverse the entire input array and perform a constant amount of work at each iteration, resulting in a time complexity of O(n).
 The average case time complexity is also O(n), assuming a random distribution of the elements in the input array.
Space Complexity:
 The algorithm performs the operation inplace, modifying the input array directly without using any extra space.
 The space used by the algorithm is therefore constant and does not depend on the size of the input array.
 The space complexity of the Brute force approach is O(1).
Twopointers:
We can use two pointers, one to track the current position in the original array, and another to track the current position in the modified array.
We iterate through the array, and whenever we encounter an element that is not equal to val
, we copy it to the modified array using
the second pointer. After we have processed all the elements, we return the index of the second pointer, which represents the number of elements
remaining in the modified array. This approach has a time complexity of O(n) and requires O(1) extra memory.
Algorithm:
 Initialize two pointers,
i
andj
, to 0. 
While
i
is less than the length of the array:
If
nums[i]
is not equal toval
, setnums[j]
tonums[i]
and incrementj
.  Increment
i
.

If
 Return
j
.
Time complexity: O(n)
Space complexity: O(1)
The time complexity is O(n) because the algorithm performs a single pass through the input array, and the number of iterations is proportional to the length of the array, which is n. In each iteration, the algorithm performs constanttime operations, such as checking the value of the current element and copying it to the appropriate position in the array. Therefore, the overall time complexity is linear in the length of the array.
The space complexity is O(1) because the algorithm modifies the input array in place, without using any additional space. The only extra space used by the algorithm is the integer variable i, which is used to keep track of the current position in the modified array, but this variable does not depend on the size of the input array, so the space complexity is constant.
Using builtin functions:
Many programming languages provide builtin functions to remove elements from arrays. For example, in Python, we can use the
remove()
method of the list class to remove all occurrences of val
from the list. This approach is easy to implement,
but it may not meet the requirement of not using extra memory, depending on how the language implements the builtin functions.
Algorithm:

Call the builtin function to remove all occurrences of
val
from the array.  Return the length of the modified array.
Note that the above code snippets modify the input array or vector in place to remove the values that equal to
val
. They use builtin functions such as Array.FindAll
in C#, list comprehension in Python,
Arrays.stream
and toArray
in Java, and std::remove
and vector::erase
in C++, to filter out the
elements that satisfy a certain condition. The resulting array or vector has the same order as the input array, except that the values that equal
to val
have been removed. The length of the resulting array or vector is returned as the output. Since the time complexity of the
builtin functions is usually implementationdependent, we cannot give a precise analysis of the time complexity. However, it is usually
reasonable to assume that the time complexity is proportional to the size of the input array or vector. The space complexity is O(1) because the
builtin functions do not use any extra space, apart from the input and output arrays or vectors.
Using recursion:
We can implement the removal of elements recursively by removing the first occurrence of val
in the array and then calling the
function recursively on the remaining part of the array. This approach has a time complexity of O(n^2) in the worst case and requires O(n) extra
memory due to the recursive call stack.
Algorithm:
 If the array is empty, return 0.

If the first element of the array is equal to
val
, remove it and return the result of recursively calling the function on the remaining part of the array.  Otherwise, increment the result of recursively calling the function on the remaining part of the array by 1 and return it.
Time complexity: O(n^2)
Space complexity: O(n)
The time complexity of the Using recursion approach is O(n^2) in the worst case, when all the elements of the array are equal to val. This is because each recursive call removes one element from the array, and there can be up to n recursive calls in the worst case. The space complexity is O(n) in the worst case, due to the recursion stack.