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:
LeetCode Solutionsnums 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.
0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100Each element is visited at most once by the left pointer and at most once by the right pointer, resulting in a linear time complexity.
We are modifying the array in-place and using only a constant amount of extra space for the temporary variable.
In this approach, we use two pointers: one starting at the beginning of the array (left) and the other at the end of the array (right). We iterate through the array using the left pointer. If the element at the left pointer is not equal to val, we increment the left pointer. If the element at the left pointer is equal to val, we swap the element at the left pointer with the element at the right pointer and then decrement the right pointer. We continue this process until the left pointer is no longer less than or equal to the right pointer, which means we have removed all occurrences of val from the array.
Each element is visited once, resulting in a linear time complexity.
We are modifying the array in-place and using only a constant amount of extra space for the variable k.
In this approach, we use a variable k as a pointer to keep track of the position for the next element that is not equal to val. While iterating through the array, if we find an element different from val, we move it to position k and increment k by 1. After the loop finishes, k represents the count of elements that satisfy the condition.
| Approach | Rating | Time Complexity | Space Complexity | Advantages | Disadvantages |
|---|---|---|---|---|---|
| Two Pointers with Temporary Variable | Minimizes writes when target values are rare (swaps from end) | Requires a temporary variable for swapping, does not preserve order | |||
| Two Pointers without Temporary Variable | Simplest and most concise code, preserves relative order of non-target elements | May perform unnecessary writes when no elements match val |
The optimal approach for this problem is Solution 2: Two Pointers without Temporary Variable, which achieves time complexity and space complexity. It simply copies non-target elements forward using a single pointer k, resulting in the cleanest and most readable code while preserving element order.
class Solution: def removeElement(self, nums: List[int], val: int) -> int: left = 0 right = len(nums) - 1
while left <= right: if nums[left] != val: left += 1 # if the current element is not equal to val, move the left pointer to the right else: # swap the current element with the element at the right pointer and move the right pointer to the left temp = nums[right] nums[right] = nums[left] nums[left] = temp
right -= 1
return leftclass Solution: def removeElement(self, nums: List[int], val: int) -> int: k = 0
for i in range(len(nums)): if nums[i] != val: nums[k] = nums[i] # move the current element to the position of k k += 1
return k