Remove Element - Leetcode Solution

Problem Link

💡 Step-by-Step Thought Process

The task is to remove all occurrences of a given value val from an array in-place and return the length of the array after removal. The order of the remaining elements does not matter, which gives us flexibility in how we rearrange the array.

The solution employs a two-pointer technique to partition the array, keeping elements not equal to val at the front. Here’s how it operates:

Initial Setup: We use two pointers: i, which iterates through the array, and n, which represents the current length of the valid array (initially the full array length). The pointer n tracks the boundary beyond which elements can be overwritten.
Processing Elements: We iterate while i is less than n. For each element at nums[i]:
- If nums[i] equals val, we replace it with the last element of the valid array (nums[n-1]) and decrement n. This effectively removes the element by reducing the valid array size, and we do not increment i since the swapped element needs to be checked.
- If nums[i] does not equal val, we keep it and increment i to move to the next element.
Result: After the loop, n represents the number of elements not equal to val, and the first n elements of the array contain the valid elements (in any order). We return n.
Why This Works: By swapping elements equal to val with the last element and shrinking the valid array size, we ensure that all elements not equal to val are retained at the front. The approach avoids extra space by reusing the array’s own space, and the order of elements is irrelevant per the problem’s constraints.
Time and Space Complexity: The solution processes each element at most twice (once when checking and possibly once after swapping), yielding a time complexity of O(n). Since it modifies the array in-place, the space complexity is O(1).

Code Solution

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        n = len(nums)

        while i < n:
            if nums[i] == val:
                nums[i] = nums[n - 1]
                n -= 1
            else:
                i += 1
        return n

        # Time: O(n)
        # Space: O(1)

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i = 0, n = nums.size();

        while (i < n) {
            if (nums[i] == val) {
                nums[i] = nums[n - 1];
                n--;
            } else {
                i++;
            }
        }
        return n;
    }
};

class Solution {
    public int removeElement(int[] nums, int val) {
        int i = 0, n = nums.length;

        while (i < n) {
            if (nums[i] == val) {
                nums[i] = nums[n - 1];
                n--;
            } else {
                i++;
            }
        }
        return n;
    }
}

var removeElement = function(nums, val) {
    let i = 0;
    let n = nums.length;

    while (i < n) {
        if (nums[i] === val) {
            nums[i] = nums[n - 1];
            n--;
        } else {
            i++;
        }
    }
    return n;
};

Detailed Explanation

Understanding the Problem

The objective of the "Remove Element" problem is to eliminate all instances of a specified value val from an array nums in-place and return the new length of the modified array. In-place means you must not use extra space for another array. Furthermore, the relative order of elements does not need to be preserved, which opens the door for more efficient strategies.

Optimal Approach: Two-Pointer Technique

This problem is efficiently solved using a two-pointer strategy. One pointer, i, scans the array from left to right, while another pointer, n, keeps track of the effective end of the array, gradually shrinking as we remove elements equal to val.

The core idea is to iterate through the array, and whenever we find an element equal to val, we overwrite it by swapping with the last unchecked element in the array (at position n - 1). After the swap, we reduce n by one, as we’ve effectively removed one occurrence of val. We do not advance the scanning pointer i in that case, since the new element at index i needs to be checked. If nums[i] is not equal to val, we simply increment i.

Example Walkthrough

Consider the input nums = [3, 2, 2, 3] with val = 3. We begin with i = 0 and n = 4. The value at index 0 is 3, so we swap it with nums[3], which is also 3. We reduce n to 3 and stay at index 0. Now nums[0] is again 3, so we swap with nums[2], which is 2. Now the array is [2, 2, 3, 3] and n = 2. Finally, we increment i through the remaining valid elements. The output is 2, and the first two elements of the array are [2, 2].

Why This Works

This solution takes advantage of the fact that the order of remaining elements doesn’t matter. By swapping with the last valid element and shrinking the effective size of the array, we remove unwanted values in constant time per operation. This avoids unnecessary shifts or deletions.

Time and Space Complexity

The algorithm has a time complexity of O(n), where n is the length of the input array. Each element is checked at most once, and swaps are done in constant time. The space complexity is O(1) since no extra space is used beyond the input array.

Conclusion

The "Remove Element" problem demonstrates the power of two-pointer techniques for in-place array modifications. By optimizing for performance and adhering to constraints, this solution balances clarity, efficiency, and correctness—making it a commonly used method in competitive programming and technical interviews.

Get Personalized Support at AlgoMap Bootcamp 💡