27. Remove Element

Quick Identifier

• Topic: arrays-hashing
• Pattern: Two Pointers (Fast / Slow Pointers)
• Hint: Use a "slow" pointer to track where the next valid element should go, and a "fast" pointer to scan the array. Ignore any element that equals val.
• Difficulty: Easy
• Companies: Amazon, Google, Apple, Microsoft, Bloomberg
• LeetCode: 27

Quick Sights

• Time Complexity: O(n). The fast pointer right scans through the array exactly once.
• Space Complexity: O(1). The problem explicitly demands an in-place solution. No extra arrays are allocated.
• Core Mechanism: Maintain two indices: left (the Writer, marking the insert position) and right (the Scanner). Start both at index 0. As right scans forward, if nums[right] is not the target val, it is a "keeper". Write this keeper to nums[left], and increment left. If nums[right] is the target val, do nothing and let right move on.

Concept Explanation

As a senior engineer, recognizing the Fast/Slow Two-Pointer pattern here is identical to LeetCode 26: Remove Duplicates from Sorted Array. The only difference is the condition that triggers a "write".

1. The In-Place Filter: You are essentially writing an array .filter() function, but you are not allowed to allocate a new array to hold the filtered results. You must overwrite the "garbage" values in the existing array.
2. The Two Roles:
   • The Scanner (right): This pointer runs ahead. Its job is to evaluate every single number. Does this number equal val? If yes, it's garbage—ignore it. If no, it's a "keeper".
   • The Writer (left): This pointer starts at 0. It points to the exact slot where the next "keeper" belongs.
3. The Handoff: When the Scanner finds a keeper, it hands it to the Writer. The Writer places the keeper in its slot, steps forward one space, and waits.
4. The Safe Overwrite: Why is it safe to overwrite elements in the same array? Because the Scanner (right) is always greater than or equal to the Writer (left). The Writer will never overwrite a number that the Scanner hasn't already evaluated.

Diagram

This flowchart outlines the Fast/Slow pointer filtering mechanism.

Study Pattern (SDE3+)

• 0–3 min: Quickly identify the Fast/Slow pointer pattern. Explain the $O(1)$ space constraint and how the left pointer naturally tracks the length of the new valid array prefix.
• Implementation pass: Initialize both left and right at 0. (Unlike problem 26 where you started at 1). Simply write nums[left] = nums[right] whenever nums[right] != val.
• 5 extension: What if the elements to remove are very rare? (e.g., nums = [1,2,3,4,5], val = 6). The current algorithm still redundantly writes nums[i] = nums[i] for every element. If the interviewer asks to optimize the number of writes, you can use a Two-Pointer technique starting from opposite ends. If nums[left] == val, you swap it with nums[right] and decrement right. This avoids unnecessary writes but does not preserve the relative order of elements (which is allowed by the problem description).

Approaches

• Brute force — Use an extra array to hold the non-target elements, then copy them back to nums. Time: $O(n)$, Space: $O(n)$. Fails the in-place requirement.
• Optimal (Fast/Slow Pointers) — Time: $O(n)$, Space: $O(1)$. Preserves relative order. (Pick this)
• Alternative Optimal (Opposite Ends) — Time: $O(n)$, Space: $O(1)$. Minimizes write operations, but scrambles relative order. (Good to mention for extra points).

Optimal Solution

Go

func removeElement(nums []int, val int) int {
	// 'left' is the Writer. It marks where the next valid element should go.
	left := 0

	// 'right' is the Scanner.
	for right := 0; right < len(nums); right++ {
		// If we find an element that we want to keep
		if nums[right] != val {
			nums[left] = nums[right] // Write it to the 'left' position
			left++                   // Move the Writer forward
		}
	}

	// The 'left' pointer now represents the length of the valid prefix
	return left
}

JavaScript

function removeElement(nums, val) {
	let left = 0; // Writer pointer

	for (let right = 0; right < nums.length; right++) {
		// If the scanner finds a "keeper"
		if (nums[right] !== val) {
			nums[left] = nums[right];
			left++;
		}
	}

	return left;
}

Walkthrough

Input: nums = [3,2,2,3], val = 3

Output: 2. The array's first 2 elements are [2,2]. (The rest of the array is ignored by the grader).

Edge Cases

• Array length is 0 (Loop won't execute, returns 0).
• Array contains only the target val (Scanner skips everything, returns 0).
• Array contains none of the target val (Scanner writes every element to its own index, returns nums.length).

Pitfalls

• Overthinking the "removal" aspect. You don't actually delete anything from memory or shorten the array's physical length. You just overwrite the garbage elements and return the integer length of the valid prefix. The grader looks at that prefix and ignores the tail.

Similar Problems

• 026. Remove Duplicates from Sorted Array — The exact same Writer/Scanner pattern, but checking against the previous element instead of a fixed val.
• 283. Move Zeroes — Another in-place array compaction using Fast/Slow pointers, but requires keeping the "removed" elements at the end of the array.

Mind-Map Tags

#two-pointers #fast-slow #in-place-compaction #arrays