Given an integer array
nums and an integer
val, remove all occurrences
nums in-place. 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
k elements of
nums should hold the final result. It does not matter what you leave beyond the
k after placing the final result in the first
k slots of
Do not allocate extra space for another array. You must do this by modifying the input array in-place with O(1) extra memory.
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
nums2 has a length of
The problem is to write a function that takes an integer array
nums and an integer
val as inputs, and removes all occurrences of
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
In other words, the function should modify the input array
nums in-place such that it contains only the elements that are not equal to
val, and return the number of such elements.
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).
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).
- 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 non-empty, or do we need to handle empty input arrays as well?
There are several approaches to solving this problem. Here are a few possible ones:
Using built-in functions
Using a stack
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)
- Initialize a variable
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
- If the current element is equal to
- 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.
- The algorithm performs the operation in-place, 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).
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.
- Initialize two pointers,
j, to 0.
iis less than the length of the array:
nums[i]is not equal to
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 constant-time 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 built-in functions:
Many programming languages provide built-in 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 built-in functions.
Call the built-in function to remove all occurrences of
valfrom 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 built-in functions such as
Array.FindAll in C#, list comprehension in Python,
toArray in Java, 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
val have been removed. The length of the resulting array or vector is returned as the output. Since the time complexity of the
built-in functions is usually implementation-dependent, 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
built-in functions do not use any extra space, apart from the input and output arrays or vectors.
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.
- 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.