Leetcode 150 | Day 2: Remove Element - Naive vs. Optimized

Leetcode 27: Remove Element

Leetcode 27 asks us to remove a specific value from an array. The value to be removed is passed in as a parameter to the function along with the array. Just as we did in Day 1, we will cover a naive approach and an optimized approach and discuss the trade-offs between them. I think in the end there's a pretty clear winner. Let's get started.

For both approaches we will use the following values:

• nums = [1, 3, 3, 2, 4]
• val = 3

---

Approach 1: Naive (For Loop + Splice)

This approach uses a for loop and leverages .splice() for removals.

Solution:

var removeElement = function(nums, val) {
    let k = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] === val) {
            nums.splice(i, 1);
            i--;
        } else {
            k++;
        }
    }
    return k;
};

We begin by initializing a variable k to 0. We then enter the for loop. The condition is standard: create a variable i initialized to 0, continue looping while i is less than nums.length to avoid going past the end of the array, and increment by 1 each time through.

Each iteration checks one condition: whether nums[i] is equal to val. If true, we call .splice() on the array. The arguments we pass to splice are i and 1. i is the index at which we want to start removing, and 1 tells splice to remove only that one element.

We then decrement i. The reason for this took me some time to wrap my brain around, so I have included a visual below to make it concrete.

The core issue is this: when splice removes an element, every element to the right shifts one index to the left. Without i--, the loop would increment i on the next iteration and skip right over the element that just shifted in. i-- counteracts that by stepping i back, so after the loop increments it, i lands exactly where the shifted element now sits.

If nums[i] !== val, we skip the splice and increment k instead. At the end we return k, which holds the count of elements remaining after all occurrences of val have been removed.

Time complexity: O(n²)

Every splice call shifts all elements to the right of the removed index, which is O(n) on its own. If every element in the array equals val, you are doing that n times. That cost adds up fast.

Space complexity: O(1)

Everything happens in place. No extra memory is allocated.

---

Approach 2: Optimized (Two Pointers)

This approach uses a two-pointer technique to solve the problem. One pointer is the fast pointer i, which moves forward on every iteration. The other is the slow pointer k, which only moves forward when a value worth keeping is found.

Solution:

var removeElement = function(nums, val) {
    let k = 0;
    for (let i = 0; i < nums.length; i++) {
        if (nums[i] !== val) {
            nums[k] = nums[i];
            k++;
        }
    }
    return k;
};

Here's a legend to aid clarity:

Here's how it works.

Step 1.

Both i and k begin at index 0. We check whether nums[i] === val. Since nums[0] is 1 and 1 !== 3, we write the value at nums[i] to nums[k]. We then increment both i and k.

Step 2.

Both i and k are now at index 1. We ask the same question: is nums[i] === val? It is. nums[1] is 3.

Step 3.

Since nums[i] === val, we do not write anything. We increment i but k stays put. This is the two-pointer pattern in action. k is now trailing behind i by one index position.

i is now at index 2. We ask our question again: is nums[i] === val? It is. Once again k stays put and i moves forward to index 3.

Step 4.

We ask our question again: is nums[i] === val? No. So we write the value at nums[i] to nums[k], then increment both i to index 4 and k to index 2.

Our array is now nums = [1, 2, 3, 2, 4].

Step 5.

i is at index 4, k is at index 2. We ask our question one final time: is nums[i] === val? No. We write the value at nums[i] to nums[k].

Our array is now nums = [1, 2, 4, 2, 4].

Since the problem asks us to return the count of elements remaining after removing val, we simply return k. The elements beyond index k are leftover and ignored. The first k elements are our answer.

Here is the final result:

Time complexity: O(n)

One pass through the array. No shifting, no splice.

Space complexity: O(1)

Also in place. No extra memory allocated.

---

Conclusion

There are genuine pros and cons to consider with each approach.

Approach 1 pros:

• More intuitive to read. The logic maps closely to how most people think about removing something.
• The array stays clean. All occurrences of val are actually removed, not just ignored.
• Shorter code.

Approach 1 cons:

• O(n²) time complexity due to repeated shifting from splice.
• Mutates indices mid-loop, which requires i-- and introduces a potential bug if forgotten.
• The cost of .splice() is hidden, making it easy to underestimate.

Approach 2 pros:

• O(n) time. One clean pass, no shifting.
• No index mutation mid-loop, simpler to reason about once the two-pointer pattern clicks.
• Scales well.

Approach 2 cons:

• The array is not truly cleaned up. Elements beyond k still exist in memory, just ignored.
• The two-pointer pattern is less intuitive at first glance, especially for newer developers.
• Returning k instead of the modified array can be confusing until you understand what the problem is actually asking for.

Both approaches solve the problem. But the time complexity difference is significant, and Approach 2 scales in a way Approach 1 simply does not. For most real-world use cases, Approach 2 is the right call.

...Day 3 coming soon