LeetCode 27 Remove Element: Two-Pointer In-Place Deletion, Interview Tips & 11 Pitfalls
This article thoroughly explains LeetCode 27 Remove Element using fast-slow and two-pointer swap approaches, covering loop invariants, boundary handling, 11 common pitfalls, 7 interview follow-up questions, and how this template applies to related problems like 26, 283, and 80.
Why a "Simple" Question Stumps Candidates
A reader failed LeetCode 27 in an interview: asked to remove all occurrences of val from an array in-place without extra space, they wrote a nested-loop O(n²) solution. When the interviewer asked "What if data volume grows?" they froze. This "harmless" easy problem hides the full two-pointer in-place compaction toolkit.
Clarify the Problem First
Before coding, confirm three points aloud:
"In-place" means O(1) space — no new array; modify nums directly.
"Remove" is not physical deletion — Java arrays have fixed length. Removal = shift kept elements to the front, return count k, treat [0, k) as valid prefix, rest is garbage.
Edge cases — empty array, all val, no val — must return 0, 0, original length respectively.
Key insight: Array deletion is fundamentally overwrite , not erase. Because arrays are contiguous and fixed-length, you cannot truly delete a slot; you overwrite it with a keeper.
Approach Evolution: Brute Force → Fast-Slow → End-Swap
Brute Force (O(n²)) — Mention, Don't Write
public int removeElement(int[] nums, int val) { int length = nums.length; for (int i = 0; i < length; i++) { if (nums[i] == val) { for (int j = i + 1; j < length; j++) { nums[j - 1] = nums[j]; } i--; length--; } } return length; }Each deletion shifts the entire suffix. Time O(n²). Interview note: the i-- after shift is critical — otherwise the new element shifted into position i is skipped.
Solution 1: Fast-Slow Pointers (Standard, Order-Preserving)
Core idea: read-write separation. fast (reader) scans entire array, filters elements != val. slow (writer) points to next write position for valid elements.
Mnemonic: fast is the "eye", slow is the "pen" — eye scans all, pen writes only keepers.
Walk-through: nums = [3,2,2,3], val = 3
Round 1: fast=0, nums[0]=3 == val ❌ → skip, fast advances alone, slow=0, valid prefix [] Round 2: fast=1, nums[1]=2 != val ✅ → copy to slow, slow=1, valid prefix [2] Round 3: fast=2, nums[2]=2 != val ✅ → copy to slow, slow=2, valid prefix [2,2] Round 4: fast=3, nums[3]=3 == val ❌ → skip, fast advances alone, slow=2, valid prefix [2,2] Return slow = 2; first two slots are [2,2], rest garbage.
Core Code (Java)
class Solution { public int removeElement(int[] nums, int val) { int slow = 0; for (int fast = 0; fast < nums.length; fast++) { if (nums[fast] != val) { nums[slow++] = nums[fast]; } } return slow; } }Why It's Correct (Loop Invariant)
Loop invariant: At any moment, [0, slow) contains exactly the valid (non- val ) elements seen so far, in original order. slow never exceeds fast , so we never overwrite unread data.
Self-assignment safe? When slow == fast, nums[slow] = nums[fast] is a no-op. If no val exists, entire array self-assigns, returns n — correct.
Why no data loss? fast ≥ slow always. The overwritten slot either held val (discarded) or was already read by fast.
Why return slow not slow+1 ? slow is "next write index" starting at 0; after each write it increments. At end it equals the count of valid elements. Empty array → slow=0 → correct.
Solution 2: End-Swap (Bonus, Fewer Writes When val Is Rare)
Motivation: Fast-slow writes every keeper, even when val is sparse. Example: nums=[1,2,3,4,5], val=5 — fast-slow does 4 self-assignments. Writes = n - k (keepers).
Problem allows order change. Swap from end: each hit writes once, total writes = k (deletions).
Core Idea: Tail Fills Hole
leftscans left→right, stops on val.
Overwrite nums[left] with last unjudged element ( nums[--right]), shrink logical length.
Critical: After overwrite, do not advance left — the swapped-in element is unchecked and may be val again.
Core Code (Open Interval, Recommended)
class Solution { public int removeElement(int[] nums, int val) { int left = 0, right = nums.length; while (left < right) { if (nums[left] == val) { nums[left] = nums[--right]; // left stays, re-check } else { left++; } } return left; } }Why Open Interval ( right = length + --right )?
Avoids right = length-1 underflow on empty array.
Loop condition left < right naturally handles all boundaries.
Walk-through: nums=[3,2,2,3], val=3
i=0 hit 3 → tail 3 fills → [3,2,2 | 3] n=3, i stays i=0 re-check, hit 3 → tail 2 fills → [2,2 | 2,3] n=2, i stays i=0 = 2 ✅ → i=1 i=1 = 2 ✅ → i=2 == n, end, return 2 ✅Swapped-in element can re-hit val — hence left must not advance.
Longer Example: nums=[0,1,2,2,3,0,4,2], val=2
left=0: 0≠2 → left=1 left=1: 1≠2 → left=2 left=2: 2==2 → tail 2 fills, right=7, left stays (still 2!) left=2: 2==2 → tail 4 fills, right=6, left stays → [0,1,4,2,3,0,4,2] left=2: 4≠2 → left=3 left=3: 2==2 → tail 0 fills, right=5, left stays → [0,1,4,0,3,0,4,2] left=3: 0≠2 → left=4 left=4: 3≠2 → left=5 == right, end, return 5 ✅First 5: [0,1,4,0,3] — order changed, allowed.
Two Other Variants (Recognize, Don't Memorize)
Closed interval: right = length-1, condition left <= right, post-decrement right--.
Double-while: Right pointer pre-finds a confirmed keeper, then overwrite and left++ safely.
All three differ only in: (1) open vs closed interval (sets initial right and loop condition), (2) whether left advances after overwrite (depends on whether swapped-in element is pre-validated). Master these two decisions and any variant works.
Choosing Between the Two — Cheat Sheet
Time: both O(n)
Space: both O(1)
Order Preserved? Fast-slow ✅ stable; End-swap ❌ scrambled
Writes: Fast-slow n - k (keepers); End-swap k (deletions)
Best For: Fast-slow — general, order required, val dense; End-swap — order irrelevant, val sparse
Interview Weight: Fast-slow ⭐⭐⭐⭐⭐ must write first; End-swap ⭐⭐⭐⭐ proactive bonus
One-line decision: Need order → fast-slow; order free & val rare → end-swap cuts writes from n-k to k.
Interview script: "If business requires original order, I use fast-slow; if only count matters, order can change, and val is infrequent, I use end-swap to reduce writes from n-k to k ."
11-Pitfall Cheat Sheet
Array fixed length, can't physically delete — Symptom: try Arrays.copyOf or new array → O(n) space. Fix: logical length k; [0,k) valid, overwrite instead of delete.
Brute-force shifting → O(n²) — Symptom: each delete shifts suffix, TLE on large data. Fix: read-write separation: fast scans, slow writes, single pass.
Massive self-assignment — Symptom: fast-slow writes n-1 times when val rare. Fix: switch to end-swap: writes = k.
End-swap: advance left after overwrite — Symptom: swapped-in val missed. Fix: after overwrite, do not move left ; re-check same index.
Empty array / right bound overflow — Symptom: right = length-1 fails on empty. Fix: open interval: right = length + --right.
Loop condition < vs <= — Symptom: off-by-one, out-of-bounds or missed element. Fix: open: left < right; closed: left <= right; check condition before access.
fast incremented inside branch — Symptom: nums[slow++] = nums[fast++] skips elements. Fix: fast only in for-loop header; roles separated.
Return slow+1 — Symptom: off-by-one, count too high. Fix: slow is count (next write index), return directly.
Worry about garbage tail values — Symptom: waste time zeroing tail. Fix: spec says tail unchecked; ignore.
Confuse physical vs logical length — Symptom: think array actually shrinks. Fix: return logical length; [k, len) is garbage by contract.
Skip edge-case mental run — Symptom: empty / all- val / no- val fail. Fix: mentally trace three cases before declaring done.
All three edge cases handled automatically by both solutions:
nums = [], val = 1 → 0 ✅ loop never enters nums = [3,3], val = 3 → 0 ✅ all skipped / swapped out nums = [1,2], val = 3 → 2 ✅ all kept, returned unchanged7 High-Frequency Interview Follow-Ups
Q1: Why return length only, not actually delete?
Java array length fixed at new . Physical delete impossible. Even ArrayList.remove() uses System.arraycopy for in-place compaction + sets last to null for GC. "Logical length" is the universal pattern for array deletion.
Q2: Connection to JDK source?
ArrayList.removeIf(Predicate) is the production version: skip leading non-deletes, batch-mark, then single System.arraycopy compaction — same "reduce useless moves" core. Mentioning this impresses interviewers.
Q3: Can I use Stream or new array?
Code compiles but fails the constraint . filter().toArray() uses O(n) extra space, violates "in-place". This question tests space awareness; using Stream signals you missed the requirement.
Q4: If order must be kept, can I still use end-swap?
No. End-swap moves tail elements forward, scrambling order. Order required → must use fast-slow. Say this proactively.
Q5: Why O(n)?
Array scanned constant times, no nested loops. Each element visited at most twice (read once, overwritten once) → linear.
Q6: How to prove correctness?
Loop invariant: [0, slow) always holds all valid elements seen so far, slow ≤ fast guarantees no unread data overwritten. At termination, interval equals all valid elements; edge cases covered.
Q7 (Extension): ArrayList loop deletion gotchas?
ArrayList.remove(index) shifts suffix O(n). In a forward loop, index shift causes skipped elements. Fix: iterate backwards or use Iterator.remove() . Real production bug.
One Template, Four Problems
The "in-place compaction" skeleton is identical; only the if condition changes:
27. Remove Element — keep condition: nums[fast] != val — keep ≠ target
26. Remove Duplicates from Sorted Array — keep condition: nums[fast] != nums[slow-1] — compare with last kept
283. Move Zeroes — keep condition: nums[fast] != 0 — keep non-zero, then pad zeros
80. Remove Duplicates II — keep condition: nums[fast] != nums[slow-2] — allow two, compare with 2nd-last kept
Mentioning these variants shows you grasp the pattern, not just one problem.
Closing script (last 30 sec): "I'll lead with fast-slow — stable, readable, O(n)/O(1). If you prioritize extreme write reduction and order doesn't matter, I'll add end-swap to cut writes from n-k to k . I've also verified empty, all-match, no-match boundaries."
Final habit: After coding, manually trace with an example. Interviewers fear "write-and-submit"; they love "write-then-verify".
Three Takeaways
Array "deletion" = overwrite + two-pointer write control.
First clarify "who reads, who writes" — separation yields code naturally.
"Order may change" is a signal — it invites end-swap to save writes.
This isn't a toy problem. It's the foundation of in-place algorithms — used in real high-volume data cleansing: "keep only valid records, compact in-place." Master the base; everything else is a variant.
Signed-in readers can open the original source through BestHub's protected redirect.
This article has been distilled and summarized from source material, then republished for learning and reference. If you believe it infringes your rights, please contactand we will review it promptly.
How this landed with the community
Was this worth your time?
0 Comments
Thoughtful readers leave field notes, pushback, and hard-won operational detail here.
