Remove Element from Array

Problem Statement

You are given an integer array nums and an integer val. Your task is to remove all occurrences of val from numsin-place, meaning you should modify the array directly. The relative order of the elements may change.

After removing all instances of val, return the number of elements that are not equal to val.

You do not need to worry about the elements that are beyond the new length of the array after removal. The goal is to modify the array in-place such that only the elements that are not equal to val remain in the first part of the array.

LeetCode Link

Remove Element

Constraints

0 <= nums.length <= 100
0 <= nums[i] <= 50
0 <= val <= 100

Examples

Example 1:

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

Explanation:
After removing all occurrences of val (which is 3), the array could look like [2, 2]. The length of the modified array is 2.

Example 2:

Input: [0, 1, 2, 2, 3, 0, 4, 2], val = 2
Output: 5

Explanation:
After removing all occurrences of val (which is 2), the array could look like [0, 1, 4, 0, 3]. The length of the modified array is 5.

Example 3:

Input: [1, 1, 1, 1], val = 1
Output: 0

Exaplanation:
After removing all occurrences of val (which is 1), the array becomes empty, so the length is 0.

Different Approaches

1️⃣ Two Pointer (Optimal - When Order Doesn't Matter)

Intuition:

We can overwrite elements equal to val from the end since we don't care about the order.

Idea:

• Use two pointers:
  • i (start of array)
  • n (effective array size)
• When nums[i] == val, replace nums[i] with nums[n-1] and reduce n.
• Else, increment i.

Code:

int removeElement(vector<int>& nums, int val) {
    // Step 1: Initialize index `i` to start from the beginning of the array
    int i = 0;

    // Step 2: `n` keeps track of the current size of the array (as we remove elements)
    int n = nums.size();

    // Step 3: Loop through the array while `i` is less than the current size `n`
    while (i < n) {
        // Step 4: If the current element equals the value to remove
        if (nums[i] == val) {
            // Step 5: Replace it with the last element in the current range
            nums[i] = nums[n - 1];

            // Step 6: Decrease the size of the array (`n`) by 1
            // (This effectively removes the last element we just copied)
            --n;

            // Step 7: Do NOT increase `i` here, because the new element at index `i`
            // (swapped from the end) needs to be checked again
        } else {
            // Step 8: If it's not the target value, move to the next element
            ++i;
        }
    }

    // Step 9: Return the new size of the array after removing all `val` elements
    return n;
}

Complexity Analysis:

• Time Complexity:O(n)
• Space Complexity:O(1)

2️⃣ Two Pointer (Stable Order)

Intuition:

Keep the order of remaining elements unchanged.

Approach:

1. We need to traverse through the array and whenever we encounter an element that is not equal to val, we should overwrite the elements in place, starting from the beginning of the array.
2. We can maintain a pointer i to track where the next non-val element should be placed.
3. We iterate over the array with a second pointer j, and for every element that is not equal to val, we copy it to the index i and increment i.

At the end of the process, i will represent the number of elements that are not equal to val, and the first i elements of the array will be the modified array without val.

Dry Run:

Initialization:

val = 3
       +-----+-----+-----+-----+
nums = |  3  |  2  |  2  |  3  |
       +-----+-----+-----+-----+
          0     1     2     3
i = 0

Iterate over the nums with j from 0 to n - 1

i = 0
j = 0 (loop)
val = 3

       +-----+-----+-----+-----+
nums = |  3  |  2  |  2  |  3  |
       +-----+-----+-----+-----+
          0     1     2     3
          ^
          |
          i
          j
          
    Check if nums[j] != val
             nums[0] != 3
             3 != 3
             False
             So, do nothing

i = 0
j = 1 (loop)
val = 3

       +-----+-----+-----+-----+
nums = |  3  |  2  |  2  |  3  |
       +-----+-----+-----+-----+
          0     1     2     3
          ^     ^
          |     |
          i     j
          
    Check if nums[j] != val
             nums[1] != 3
             2 != 3
             True
             set nums[i] = nums[j]
                 nums[0] = nums[1]
                 nums[0] = 2
             increment i (i = 1)

i = 1
j = 2 (loop)
val = 3

       +-----+-----+-----+-----+
nums = |  2  |  2  |  2  |  3  |
       +-----+-----+-----+-----+
          0     1     2     3
                ^     ^
                |     |
                i     j
          
    Check if nums[j] != val
             nums[2] != 3
             2 != 3
             True
             set nums[i] = nums[j]
                 nums[1] = nums[1]
                 nums[1] = 2
             increment i (i = 2)

i = 2
j = 3 (loop)
val = 3

       +-----+-----+-----+-----+
nums = |  2  |  2  |  2  |  3  |
       +-----+-----+-----+-----+
          0     1     2     3
                      ^     ^
                      |     |
                      i     j
          
    Check if nums[j] != val
             nums[2] != 3
             3 != 3
             False
             So, do nothing,

Final State:

i = 2
j = 4 (out of bounds)

       +-----+-----+-----+-----+
nums = |  2  |  2  |  2  |  3  |
       +-----+-----+-----+-----+
          0     1     2     3
                      ^          ^
                      |          |
                      i          j

i represents the new length of the array after removing all occurrences of val.
Even though nums[2] still holds 2 from a previous step, it’s not considered part of the new array length. Only the first i elements are relevant.

Code:

#include <iostream>
#include <vector>
using namespace std;

int removeElement(vector<int>& nums, int val) {
    int i = 0;  // Pointer for the next position to place non-val elements

    // Traverse through the array
    for (int j = 0; j < nums.size(); j++) {
        if (nums[j] != val) {
            nums[i] = nums[j];  // Place the non-val element at index i
            i++;  // Move i forward
        }
    }
    
    return i;  // i is the new length of the array after removing val
}

int main() {
    vector<int> nums = {3, 2, 2, 3};
    int val = 3;
    int length = removeElement(nums, val);
    
    cout << "New length: " << length << endl;  // Output should be 2
    cout << "Modified array: ";
    for (int i = 0; i < length; i++) {
        cout << nums[i] << " ";  // The array should be [2, 2]
    }
    cout << endl;
    
    return 0;
}

Complexity Analysis:

• Time Complexity: O(n), where n is the size of the array. We only iterate through the array once.
• Space Complexity: O(1), as the operation is done in-place without using extra space.