#27 Remove Element
the problem
In plain words
Remove every copy of val from nums, in place. Return k, the number of elements that are not val; nums[0..k) must hold exactly those elements, in any order. Whatever sits after them doesn't matter.
in nums = [3,2,2,3], val = 3
out 2, nums = [2,2,_,_]
in nums = [0,1,2,2,3,0,4,2], val = 2
out 5, nums = [0,1,4,0,3,_,_,_]
Any order of 0, 0, 1, 3, 4 in the first five slots is accepted.
- 0 ≤ n ≤ 100
- 0 ≤ nums[i] ≤ 50
- 0 ≤ val ≤ 100
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternTwo pointers (read / write)
Don't delete — keep. A write pointer copies every keeper forward; the unwanted values are simply overwritten or left behind after k.
solutions
From brute force to optimal
Each time you find val, shift everything after it one step left — what ArrayList.remove(i) does.
- Scan with i.
- On val: shift the tail left by one and shrink n (don't move i — a new value just arrived there).
- Otherwise i++.
Each removal shifts up to n elements.
In place.
class Solution { public int removeElement(int[] nums, int val) { int n = nums.length; int i = 0; while (i < n) { if (nums[i] == val) { for (int j = i + 1; j < n; j++) nums[j - 1] = nums[j]; // close the gap, like ArrayList.remove n--; // one element fewer } else { i++; } } return n; }}write is the next free slot; copy every value that isn't val into it.
- write = 0.
- For each read: if nums[read] != val, nums[write++] = nums[read].
- Return write.
One pass.
Two indices.
class Solution { public int removeElement(int[] nums, int val) { int write = 0; // next slot for a keeper for (int read = 0; read < nums.length; read++) { if (nums[read] != val) nums[write++] = nums[read]; } return write; }}When val is rare, pull the last element into the hole instead of copying every keeper.
- i = 0, n = length.
- If nums[i] == val: nums[i] = nums[n − 1], n--, and check slot i again.
- Otherwise i++.
Every step either moves i forward or shrinks n.
Two indices.
class Solution { public int removeElement(int[] nums, int val) { int i = 0, n = nums.length; while (i < n) { if (nums[i] == val) nums[i] = nums[--n]; // pull the last element in; check it next round else i++; } return n; }}in the room
How to say it in the interview
talk track
- Ask: does the order of the kept values matter? (No.) That opens the swap-with-last trick, which writes less when val is rare.
- State the invariant: nums[0..write) holds exactly the keepers seen so far.
traps
- Calling
ArrayList.remove(or shifting by hand) inside the loop: O(n²). - Swap-with-last: moving i forward after the swap — the value pulled in may also be val.
what they ask next
Follow-ups
What if the kept values must stay in their original order?
Use read/write — it copies keepers forward in order. Swap-with-last does not keep order.
before you submit
Edge cases to test
- Empty array → 0.
- Every element equals val → 0.
- val never appears → k = n, nothing needs to change.
- val at both ends: [2, 1, 2, 1, 2] with val = 2 → k = 2 and the first slots hold [1, 1].
practise next
Similar problems
- #283Move ZeroesEasyin Two Pointers
- #26Remove Duplicates from Sorted ArrayEasyin Two Pointers
- #80Remove Duplicates from Sorted Array IIMediumin Two Pointers