A visual guide to removing all occurrences of a value in-place using the two-pointer technique.
Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.
Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:
nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.k.Custom Judge:
The judge will test your solution with the following code:
int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
// It is sorted with no values equaling val.
int k = removeElement(nums, val); // Calls your implementation
assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
assert nums[i] == expectedNums[i];
}
If all assertions pass, then your solution will be accepted.
Example 1:
Input: nums = [3,2,2,3], val = 3 Output: 2, nums = [2,2,_,_] Explanation: Your function should return k = 2, with the first two elements of nums being 2. It does not matter what you leave beyond the returned k (hence they are underscores).
Example 2:
Input: nums = [0,1,2,2,3,0,4,2], val = 2 Output: 5, nums = [0,1,4,0,3,_,_,_] Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4. Note that the five elements can be returned in any order. It does not matter what you leave beyond the returned k (hence they are underscores).
Constraints:
0 <= nums.length <= 1000 <= nums[i] <= 500 <= val <= 100The 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++; } }
// Brute force: O(n^2) time, O(1) space n := len(nums) i := 0 for i < n { if nums[i] == val { for j := i; j < n-1; j++ { nums[j] = nums[j+1] // shift left } n-- } else { i++ } }
# Brute force: O(n^2) time, O(1) space n = len(nums) i = 0 while i < n: if nums[i] == val: for j in range(i, n - 1): nums[j] = nums[j + 1] # shift left n -= 1 else: i += 1
// Brute force: O(n^2) time, O(1) space let mut n = nums.len(); let mut i = 0; while i < n { if nums[i] == val { for j in i..n-1 { nums[j] = nums[j+1]; // shift left } n -= 1; } else { i += 1; } }
// Brute force: O(n^2) time, O(1) space let n = nums.length; let i = 0; while (i < n) { if (nums[i] === val) { for (let 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; } }
func removeElement(nums []int, val int) int { // slow = write position for kept elements slow := 0 // fast reads every element in the array for fast := 0; fast < len(nums); 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 }
class Solution: def remove_element(self, nums: list[int], val: int) -> int: # slow = write position for kept elements slow = 0 # fast reads every element in the array for fast in range(len(nums)): # Only keep elements that are NOT the target if nums[fast] != val: nums[slow] = nums[fast] # copy to write position slow += 1 # advance write position # If nums[fast] == val, just skip it # slow is the count of non-val elements return slow
impl Solution { pub fn remove_element(nums: &mut Vec<i32>, val: i32) -> i32 { // slow = write position for kept elements let mut slow = 0; // fast reads every element in the array for fast in 0..nums.len() { // Only keep elements that are NOT the target if nums[fast] != val { nums[slow] = nums[fast]; // copy to write position slow += 1; // advance write position } // If nums[fast] == val, just skip it } // slow is the count of non-val elements slow as i32 } }
function removeElement(nums: number[], val: number): number { // slow = write position for kept elements let slow = 0; // fast reads every element in the array for (let 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 O(n) time. The slow pointer writes only non-target values, performing at most n copies. We use only a constant number of variables for O(1) extra space -- a massive improvement over the O(n2) brute force that shifts elements on each removal.
Each time the target value is found, every subsequent element is shifted left by one position -- an O(n) operation. In the worst case (all elements are the target), this shift happens n times, yielding O(n2) total. No extra memory beyond loop variables.
The fast pointer scans every element once while the slow pointer writes only non-target values. Each element is read once and written at most once, giving O(n) total work. Only two index variables are used -- no shifting, no extra arrays.
For rare targets, an alternative "swap with the end" approach minimizes writes -- still O(n) but fewer copy operations. When the target value appears infrequently, swapping nums[slow] with nums[n-1] and shrinking the array avoids unnecessary copying. Problems #26 and #27 share the same read/write pointer pattern; the only difference is the condition (nums[fast] != nums[slow] vs. nums[fast] != val).
Review these before coding to avoid predictable interview regressions.
Wrong move: Advancing both pointers shrinks the search space too aggressively and skips candidates.
Usually fails on: A valid pair can be skipped when only one side should move.
Fix: Move exactly one pointer per decision branch based on invariant.