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:

text
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.

Core Insight for Remove Element

The key intuition for the optimal LeetCode 27 solution is to decouple the process of finding elements from the process of keeping elements.

In the brute force approach, the inefficiency stems from shifting elements repeatedly. However, we don't actually need to "delete" the bad elements; we only need to ensure the good elements end up at the front of the array.

We can maintain a Writer Pointer (often called slow or k) that points to the position where the next valid element should be placed. Simultaneously, a Reader Pointer (loop iterator) scans the array.

The Invariant: At any point in the execution, the subarray nums[0...writer-1] contains all the values found so far that are not equal to val.

Visual Description: Imagine the array as a single lane of memory. The reader pointer moves forward one step at a time, examining every number.

• If the reader sees a value equal to val, it ignores it (effectively "removing" it by not saving it).
• If the reader sees a value not equal to val, it copies that value to the location indicated by the writer pointer, and then the writer advances.

This ensures that valid elements are packed tightly at the beginning of the array, while the "garbage" or redundant data is left in the unvisited or overwritten section beyond the writer.

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).

Reference Implementation

C++ Solution for LeetCode 27

cpp
class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int writer = 0;
        
        // Reader iterates through the entire array
        for (int reader = 0; reader < nums.size(); reader++) {
            // If the current element is not the target value
            if (nums[reader] != val) {
                // Copy it to the writer position
                nums[writer] = nums[reader];
                // Advance the writer
                writer++;
            }
        }
        
        // writer represents the new length of the valid array
        return writer;
    }
};

Java Solution for LeetCode 27

java
class Solution {
    public int removeElement(int[] nums, int val) {
        int writer = 0;
        
        // Reader iterates through the entire array
        for (int reader = 0; reader < nums.length; reader++) {
            // If the current element is not the target value
            if (nums[reader] != val) {
                // Copy it to the writer position
                nums[writer] = nums[reader];
                // Advance the writer
                writer++;
            }
        }
        
        return writer;
    }
}

Python Solution for LeetCode 27

python
class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        writer = 0
        
        # Reader iterates through the entire array
        for reader in range(len(nums)):
            # If the current element is not the target value
            if nums[reader] != val:
                # Copy it to the writer position
                nums[writer] = nums[reader]
                # Advance the writer
                writer += 1
                
        return writer