Remove Element

LeetCode 27: Remove Element Solution & Explanation

Problem Overview

TL;DR: Use a "writer" pointer to build the valid array in the front, while a "reader" pointer scans the input, effectively overwriting unwanted values.

The LeetCode 27 problem, Remove Element, asks us to filter an integer array nums by removing all occurrences of a specific value val. Crucially, this operation must be performed in-place, meaning we cannot allocate a new array to store the result. We must modify the existing array such that the first k elements are the values that do not equal val. The function then returns k, the count of valid elements. The order of the remaining elements does not matter.

This is a classic interview question that tests a candidate's ability to manipulate memory references and array indices efficiently.

Brute Force Approach for Remove Element

The most intuitive way to solve Remove Element without knowledge of specific patterns is to mimic how a human might physically remove an item from a list. When we encounter the value val, we remove it and shift all subsequent elements one position to the left to fill the gap.

Naive Algorithm:

1. Iterate through the array.
2. If nums[i] equals val:
   • Shift every element from i + 1 to the end of the array one step to the left.
   • Decrease the array length variable.
   • Decrement the iterator i so that we re-check the current position (since a new value has shifted into it).

Pseudo-code:

k = length of nums
i = 0
while i < k:
    if nums[i] == val:
        for j from i to k - 2:
            nums[j] = nums[j + 1]
        k = k - 1
    else:
        i = i + 1
return k

Time Complexity: $O(N^2)$. In the worst case (e.g., removing all elements), for every element we remove, we perform a shift operation that touches the remaining elements. Why it fails: While this might pass on very small constraints ($N=100$), it is fundamentally inefficient. In a serious interview setting, an $O(N^2)$ solution for a linear array problem is generally considered a failure because it does not utilize the available structural properties of the array.

Algorithm Strategy: Two Pointer Patterns

1. Initialize Pointers:

   • Initialize an integer writer to 0. This tracks the index where the next non-val element will be written.
   • The reader will be the loop variable iterating from 0 to nums.length - 1.

2. Iterate and Filter:

   • Start a loop where reader traverses the array.
   • Check the condition: if (nums[reader] != val).

3. Update In-Place:

   • If the condition is met (the value is valid), assign nums[writer] = nums[reader].
   • Increment writer by 1.
   • (Note: If reader and writer are at the same index, this assignment effectively does nothing, which is fine. If they are different, it overwrites an old or invalid value).

4. Skip Invalid Values:

   • If nums[reader] == val, do nothing. The reader advances, but the writer stays put. This effectively skips the unwanted value.

5. Return Result:

   • After the loop finishes, return writer. This value represents the number of valid elements and the new logical length of the array.

Execution Flow

Let's trace the algorithm with nums = [3, 2, 2, 3] and val = 3.

1. Start: writer = 0, reader = 0.
2. Iteration 1 (reader = 0):
   • nums[0] is 3.
   • 3 == val. Condition 3 != 3 is False.
   • Action: Skip. writer remains 0.
3. Iteration 2 (reader = 1):
   • nums[1] is 2.
   • 2 != val. Condition 2 != 3 is True.
   • Action: nums[writer] = nums[reader] $\rightarrow$ nums[0] = 2.
   • Increment writer to 1.
   • Array State: [2, 2, 2, 3] (Note: the 2 at index 1 is copied to index 0).
4. Iteration 3 (reader = 2):
   • nums[2] is 2.
   • 2 != val. Condition 2 != 3 is True.
   • Action: nums[writer] = nums[reader] $\rightarrow$ nums[1] = 2.
   • Increment writer to 2.
   • Array State: [2, 2, 2, 3].
5. Iteration 4 (reader = 3):
   • nums[3] is 3.
   • 3 == val. Condition 3 != 3 is False.
   • Action: Skip. writer remains 2.
6. End: Loop finishes. Return writer (2).
   • The first 2 elements are [2, 2]. Correct.

Proof of Correctness

The correctness relies on the loop invariant: "All elements in nums[0...writer-1] are valid elements found in nums[0...reader-1]."

• Initialization: Before the loop, writer is 0. The range is empty, so the invariant holds vacuously.
• Maintenance: In each step, if nums[reader] is valid, we append it to the writer position and extend the valid range. If nums[reader] is invalid, we do not extend the valid range.
• Termination: When the loop ends, reader has scanned the entire array. Therefore, nums[0...writer-1] contains all valid elements from the original array, preserving their relative order (though relative order is not strictly required by this problem, this specific algorithm preserves it).

Pattern Reuse Notes

The Two Pointers - In-place Array Modification pattern is highly reusable. Understanding the writer/reader logic is crucial for the following problems:

• LeetCode 26: Remove Duplicates from Sorted Array: Instead of filtering by a specific value val, the condition checks if the current number is different from the previous unique number.
• LeetCode 283: Move Zeroes: This is almost identical to Remove Element. You "remove" zeroes using the writer pointer, then fill the remainder of the array with zeroes after the loop.
• LeetCode 80: Remove Duplicates from Sorted Array II: A variation where at most two duplicates are allowed. The logic remains the same, but the condition for the writer pointer checks nums[writer-2].
• LeetCode 75: Sort Colors: A more complex variation using three pointers to partition the array into three sections (0s, 1s, and 2s) in a single pass.

Reference Implementation

C++ Solution for LeetCode 27

1class Solution {
2public:
3    int removeElement(vector<int>& nums, int val) {
4        int writer = 0;
5        
6        // Reader iterates through the entire array
7        for (int reader = 0; reader < nums.size(); reader++) {
8            // If the current element is not the target value
9            if (nums[reader] != val) {
10                // Copy it to the writer position
11                nums[writer] = nums[reader];
12                // Advance the writer
13                writer++;
14            }
15        }
16        
17        // writer represents the new length of the valid array
18        return writer;
19    }
20};

Java Solution for LeetCode 27

1class Solution {
2    public int removeElement(int[] nums, int val) {
3        int writer = 0;
4        
5        // Reader iterates through the entire array
6        for (int reader = 0; reader < nums.length; reader++) {
7            // If the current element is not the target value
8            if (nums[reader] != val) {
9                // Copy it to the writer position
10                nums[writer] = nums[reader];
11                // Advance the writer
12                writer++;
13            }
14        }
15        
16        return writer;
17    }
18}

Python Solution for LeetCode 27

1class Solution:
2    def removeElement(self, nums: List[int], val: int) -> int:
3        writer = 0
4        
5        # Reader iterates through the entire array
6        for reader in range(len(nums)):
7            # If the current element is not the target value
8            if nums[reader] != val:
9                # Copy it to the writer position
10                nums[writer] = nums[reader]
11                # Advance the writer
12                writer += 1
13                
14        return writer