Remove Element
Problem
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place and return the new length of the array after removal. The order of elements can be changed, and elements beyond the new length are not important.
- 0 ≤ nums.length ≤ 100
- 0 ≤ nums[i] ≤ 50
- 0 ≤ val ≤ 100
Example
nums = [3,2,2,3], val = 32The algorithm scans through nums, skipping elements equal to val. It overwrites elements equal to val by shifting non-val elements forward. After processing, the first two elements are 2 and 2, and the returned length is 2. Elements beyond the new length are irrelevant.
Approach
Straightforward Solution
A naive approach would create a new array and copy over elements not equal to val, which uses extra space and violates the in-place constraint.
Core Observation
The problem requires removing elements equal to val in-place, which means overwriting unwanted elements with wanted ones while maintaining a valid prefix of the array.
Path to Optimal
The key insight is to use two pointers: one to read through the array and another to write the next valid element. When the read pointer encounters an element not equal to val, it writes it at the write pointer's position and increments the write pointer. This compacts all valid elements at the front of the array.
Optimal Approach
Iterate through nums with a read pointer. For each element not equal to val, copy it to the write pointer's position and increment write. After the loop, write points to the new length of the array without val elements.
Time
O(n)
The algorithm makes a single pass through the array with the read pointer, performing constant-time operations per element.
Space
O(1)
Only two integer pointers are used; no additional data structures are allocated, satisfying the in-place requirement.
Pattern Spotlight
Two Pointers (In-Place Filtering)
Use one pointer to scan all elements and another to track the position to write valid elements, effectively overwriting unwanted elements and compacting the array in a single pass.
Solution
| 1 | class Solution: |
| 2 | def removeElement(self, nums: List[int], val: int) -> int: |
| 3 | |
| 4 | write = 0 |
| 5 | |
| 6 | for read in range(len(nums)): |
| 7 | |
| 8 | if nums[read] != val: |
| 9 | nums[write] = nums[read] |
| 10 | write += 1 |
| 11 | |
| 12 | return write |
Step-by-Step Solution
Traverse Array and Overwrite Non-Val Elements
| 4 | write = 0 |
| 6 | for read in range(len(nums)): |
| 8 | if nums[read] != val: |
| 9 | nums[write] = nums[read] |
| 10 | write += 1 |
Objective
To iterate through the array and overwrite elements equal to val by shifting valid elements forward.
Key Insight
By maintaining a write pointer that only advances when a non-val element is found, the algorithm compacts all valid elements at the front of the array. This avoids extra space and preserves the in-place constraint. The read pointer scans every element, ensuring no valid element is missed.
Interview Quick-Check
Core Logic
Use two pointers: read scans all elements, write tracks where to place the next valid element, enabling in-place filtering.
State & Boundaries
The write pointer always points to the next position to write a valid element, ensuring no overwriting of unprocessed elements.
Common Pitfalls & Bugs
Incrementing the write pointer unconditionally or failing to check for val leads to incorrect results or overwriting valid elements.
Return New Length After Removal
| 12 | return write |
Objective
To return the count of elements remaining after removal of val.
Key Insight
The write pointer's final position represents the number of valid elements copied to the front of the array. Returning this value provides the new length of the array without val elements, fulfilling the problem's requirement.
Interview Quick-Check
Core Logic
Return the write pointer as the new length, since it counts how many valid elements have been placed.
Line Analysis
This solution has 2 Critical lines interviewers watch for.
if nums[read] != val:Check if the current element is not equal to val.
This conditional filters out unwanted elements, allowing only valid elements to be copied forward.
nums[write] = nums[read]Overwrite the element at the write pointer with the current valid element.
This assignment compacts the array by moving valid elements forward, overwriting elements equal to val without extra space.
write = 0Initialize the write pointer to track the position for the next valid element.
The write pointer marks the next index where a non-val element should be placed, enabling in-place compaction of the array.
return writeReturn the count of valid elements after removal.
The write pointer's final value represents the new length of the array without val elements, fulfilling the problem's contract.
write += 1Increment the write pointer after placing a valid element.
Advancing the write pointer ensures the next valid element is placed in the correct position, maintaining a contiguous block of valid elements.
for read in range(len(nums)):Iterate through the array with the read pointer.
The read pointer scans every element to determine if it should be kept or removed, ensuring all elements are processed exactly once.
Test Your Understanding
Why does the write pointer only increment when a non-val element is found?
Because the write pointer marks the position to place the next valid element; incrementing it only when a valid element is found ensures that all valid elements are compacted at the front without gaps.
Related Problems
Two Pointers pattern
Don't just read it. Drill it.
Reconstruct Remove Element from memory until it sticks. AlgoDrill blanks out key lines and makes you fill them back in, step by step.
Unlock the Remove Element drill