EasyNeetCode150ArrayTwo Pointers
Remove Element
Remove all occurrences of val in nums in-place. Return count of elements not equal to val.
Examples
Input
nums = [3,2,2,3], val = 3
Output
2
First two elements are [2,2].
Constraints
- •
0<=nums.length<=100 - •
0<=nums[i]<=50 - •
0<=val<=100
Approaches
New array then copy back.
CodeT: O(n) | S: O(n)
def removeElement(nums, val):
t=[x for x in nums if x!=val]
for i in range(len(t)): nums[i]=t[i]
return len(t)Write pointer for non-val.
CodeT: O(n) | S: O(1)
def removeElement(nums, val):
k=0
for i in range(len(nums)):
if nums[i]!=val: nums[k]=nums[i]; k+=1
return kSwap from end to fill gaps.
Diagram
swap from end when val found
CodeT: O(n) | S: O(1)
def removeElement(nums, val):
l,r=0,len(nums)
while l<r:
if nums[l]==val: nums[l]=nums[r-1]; r-=1
else: l+=1
return lComplexity Comparison
| Approach | Time | Space | Description |
|---|---|---|---|
| Brute Force | O(n) | O(n) | New array then copy back. |
| Two Pointers | O(n) | O(1) | Write pointer for non-val. |
| Two Pointers - Swap | O(n) | O(1) | Swap from end to fill gaps. |
Brute Force
T: O(n)S: O(n)
New array then copy back.
Two Pointers
T: O(n)S: O(1)
Write pointer for non-val.
Two Pointers - Swap
T: O(n)S: O(1)
Swap from end to fill gaps.
Common Mistakes
Not handling all elements being val
Using extra space in-place problem
Forgetting return count