A visual guide to removing all occurrences of a value in-place using the two-pointer technique.
The naive approach: when you find the target value, shift every element after it one position to the left. This fills the gap but requires moving many elements repeatedly.
This works but each removal causes an O(n) shift, making the worst case O(nĀ²). We can do much better.
// Brute force: O(n^2) time, O(1) space int n = nums.length; for (int i = 0; i < n; ) { if (nums[i] == val) { for (int j = i; j < n - 1; j++) nums[j] = nums[j + 1]; // shift left n--; } else { i++; } }
Instead of shifting elements, use two pointers: slow tracks where to write, fast reads every element. When fast sees a non-target value, copy it to the slow position.
Both pointers start at index 0. The fast pointer checks each element. If it is not the target, we write it at the slow position and advance both. If it is the target, only fast advances.
0..slow-1 are kept values.Key difference from #26: In Remove Duplicates, we compare nums[fast] vs nums[slow]. Here, we compare nums[fast] vs val. Also, both pointers start at 0 (not slow=0, fast=1) because the first element could be the target.
Let's trace through [3, 2, 2, 3] with val = 3:
3 == val ā skip! Only fast advances.
2 != 3 ā copy! nums[0] = 2, then slow++.
2 != 3 ā copy! nums[1] = 2, then slow++.
3 == val ā skip!
Loop never runs, slow stays at 0. Return 0.
val=3. Fast always skips. Slow never advances. Return 0.
val=3. Every element is copied. Slow reaches 4. Array is unchanged.
class Solution { public int removeElement(int[] nums, int val) { // slow = write position for kept elements int slow = 0; // fast reads every element in the array for (int fast = 0; fast < nums.length; fast++) { // Only keep elements that are NOT the target if (nums[fast] != val) { nums[slow] = nums[fast]; // copy to write position slow++; // advance write position } // If nums[fast] == val, just skip it } // slow is the count of non-val elements return slow; } }
Subtle difference from #26: Here slow starts at 0 and represents "how many elements we've kept" (the next write index). In #26, slow starts at 0 and represents "index of the last unique element." That's why #26 returns slow + 1 but this returns just slow.
Enter an array and a target value, then step through the algorithm to see the slow and fast pointers in action.
The fast pointer visits each element exactly once, giving us O(n) time. We use only a constant number of variables for O(1) extra space. A massive improvement over the O(nĀ²) brute force.
Pattern recognition: Problems #26 and #27 both use the same "slow/fast read-write pointer" pattern. The only difference is the condition: #26 checks nums[fast] != nums[slow] (new unique), while #27 checks nums[fast] != val (not the target). Recognizing this shared pattern is key to solving similar in-place array problems quickly.