Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.
Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:
nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.k.Custom Judge:
The judge will test your solution with the following code:
int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
// It is sorted with no values equaling val.
int k = removeElement(nums, val); // Calls your implementation
assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.
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).
Constraints:
0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100The key challenge in #27 Remove Element is modifying the array in-place while removing all occurrences of a given value. Since the order of the remaining elements does not necessarily matter, this problem is commonly solved using the two pointers technique.
A common idea is to maintain a write pointer that tracks where the next valid element should be placed. As you iterate through the array with another pointer, every element that is not equal to the target value is copied to the write position. This effectively compacts all valid elements at the beginning of the array while ignoring the unwanted ones. The final position of the write pointer represents the new length.
An alternative variation swaps unwanted values with elements from the end of the array to reduce unnecessary shifts.
Both approaches run in O(n) time since the array is scanned once, and they use O(1) extra space because all modifications happen directly within the input array.
| Approach | Time Complexity | Space Complexity |
|---|---|---|
| Two Pointers (Overwrite Valid Elements) | O(n) | O(1) |
| Swap With End Technique | O(n) | O(1) |
NeetCode
Use these hints if you're stuck. Try solving on your own first.
The problem statement clearly asks us to modify the array in-place and it also says that the element beyond the new length of the array can be anything. Given an element, we need to remove all the occurrences of it from the array. We don't technically need to <b>remove</b> that element per-say, right?
We can move all the occurrences of this element to the end of the array. Use two pointers! <br><img src="https://assets.leetcode.com/uploads/2019/10/20/hint_remove_element.png" width="500"/>
Yet another direction of thought is to consider the elements to be removed as non-existent. In a single pass, if we keep copying the visible elements in-place, that should also solve this problem for us.
In this approach, we use two pointers starting at the beginning of the array. One pointer, called 'i', iterates over each element of the array, while the second pointer, called 'j', records the position of where to insert a new element that is not equal to 'val'. Whenever we encounter an element not equal to 'val', we place it at the position pointed by 'j' and increment 'j'. The final value of 'j' will give us the length of the modified array where elements are not equal to 'val'.
Time Complexity: O(n), where n is the length of nums.
Space Complexity: O(1), in-place manipulation of the array.
1#include <stdio.h>
2
3int removeElement(int* nums, int numsSize, int val) {
4 int j = 0;
5This C solution uses two pointers. The 'i' pointer traverses the entire array, while 'j' records the positions to insert non-'val' elements. Elements equal to 'val' are ignored, effectively 'removing' them.
This method uses a two-pointer technique but in a different manner. Here, one pointer (i) starts from the beginning and the other pointer (end) starts from the end of the array. As long as i <= end, we check each element. If nums[i] equals val, we swap it with the element at nums[end] and decrement end. If not, increment i. This ensures that values to be removed accumulate at the end of the array, and relevant values are compacted at the front.
Time Complexity: O(n), where n is the size of nums.
Space Complexity: O(1), swaps happen within nums.
1
Watch expert explanations and walkthroughs
Practice problems asked by these companies to ace your technical interviews.
Explore More ProblemsJot down your thoughts, approach, and key learnings
Yes, variations of in-place array manipulation problems like Remove Element frequently appear in technical interviews at FAANG and other tech companies. They test understanding of pointer manipulation, array traversal, and space optimization.
The optimal approach uses the two pointers technique. One pointer scans the array while another keeps track of where the next valid element should be written. This allows the array to be modified in-place with O(n) time and O(1) extra space.
The problem is primarily solved using arrays along with the two pointers technique. Since the task requires in-place modification and minimal extra memory, additional data structures like hash maps are unnecessary.
Two pointers help efficiently track which elements should remain in the array while iterating through it only once. This technique avoids extra memory and keeps the algorithm simple and efficient.
This C solution uses an in-place swapping mechanism to manage elements. When the desired element is found, it is swapped with the back-most unchecked item, expanding backward.