Remove Element
Asked at Amazon
Problem
Given an integer array nums and an integer val, remove all occurrences of val in-place and return the new length of the array. The relative order of elements may change.
Asked At
| Company | Difficulty | |
|---|---|---|
| Amazon | EASY | View all Amazon questions → |
How to Think About It
Brute force: shift elements left every time you find val, causing O(n^2) time.
Use two pointers: one for scanning and one for writing the next valid element.
If the current element equals val, skip it; otherwise write it to the write pointer.
The write pointer always points to the next position for a valid element.
After the scan, the write pointer equals the new length.
Optimal Approach
Maintain a write pointer initialized to zero. Iterate through the array with a read pointer. Whenever the read pointer encounters a value not equal to val, copy it to the write pointer position and increment the write pointer. At the end, the write pointer is the new length of the modified array. This runs in O(n) time with O(1) space.
What Trips People Up in Real Interviews
Confirm the order of remaining elements does not matter.
Ask if you must do it in O(1) extra space (yes, in-place).
Explain the two-pointer approach clearly before coding.
Handle edge cases: all elements are val, no elements are val.
Mention that swapping approach also works and avoids shifts.
Solution Code
def removeElement(nums, val):
write = 0
for num in nums:
if num != val:
nums[write] = num
write += 1
return writeFrequently Asked Questions
What is the Remove Element problem?
Given an integer array nums and an integer val, remove all occurrences of val in-place and return the new length of the array. The relative order of elements may change.
How do you solve Remove Element?
The optimal approach is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
What companies ask Remove Element?
Remove Element is asked at Amazon. It is a easy difficulty problem.
What are common mistakes on Remove Element?
- Confirm the order of remaining elements does not matter.
- Ask if you must do it in O(1) extra space (yes, in-place).
- Explain the two-pointer approach clearly before coding.
- Handle edge cases: all elements are val, no elements are val.
- Mention that swapping approach also works and avoids shifts.