Problem Understanding

The challenge requires removing specific values from an array while meeting these constraints:

• Use only O(1) additional space and modify the input array in-place
• Element ordering can be changed
• Focus only on elements within the new length boundary

The solution will be validated using code similar to:

int result_length = removeElement(input_array, target_value);
for (int index = 0; index < result_length; index++) {
    display(input_array[index]);
}

Solution Approaches

Brute Force Method

The mosst straightforward approach uses nested loops for element removal.

Two Pointer Technique - Slow-Fast Approach

Achieve better time complexity by using two pointers. This ensures at most two traversals of the sequence. Think of it as two people crossing a bridge where one person (fast pointer) checks each plank and passes good planks to the second person (slow pointer).

Optimized Two Pointer - Left-Right Approach

Further optimizaton allows completion with at most one sequence traversal using left and right pointers.

Implementation Solutions

Brute Force Solution

class Solution {
public:
    int removeElement(vector<int>& data, int target) {
        int current_size = data.size();
        
        for (int pos = 0; pos < current_size; pos++) {
            if (data[pos] == target) {
                for (int shift_pos = pos; shift_pos < current_size - 1; shift_pos++) {
                    data[shift_pos] = data[shift_pos + 1];
                }
                current_size--;
                pos--;
            }
        }
        return current_size;
    }
};

Two Pointer - Slow-Fast Method

class Solution {
public:
    int removeElement(vector<int>& data, int target) {
        int write_index = 0;
        
        for (int read_index = 0; read_index < data.size(); read_index++) {
            if (data[read_index] != target) {
                data[write_index] = data[read_index];
                write_index++;
            }
        }
        return write_index;
    }
};

Two Pointer - Left-Right Method

Using for loop:

class Solution {
public:
    int removeElement(vector<int>& data, int target) {
        int start = 0;
        int end = data.size() - 1;
        
        for (start; start <= end; start++) {
            if (data[start] == target) {
                data[start] = data[end];
                end--;
                start--;
            }
        }
        return start;
    }
};

Using while loop:

class Solution {
public:
    int removeElement(vector<int>& data, int target) {
        int start = 0;
        int end = data.size() - 1;
        
        while (start <= end) {
            if (data[start] == target) {
                data[start] = data[end];
                end--;
            } else {
                start++;
            }
        }
        return start;
    }
};

Important Considerations

Increment Operations

Three ways to increase variable value by 1:

• Pre-increment (++variable): increment first, then use
• Post-increment (variable++): use first, then increment
• Addition assignment (variable += 1): direct addition

Array Shifting Operations

When shifting all elements forward by one position, pay attention to boundaries due to operations like array[j] = array[j+1]:

for (int j = i; j < size - 1; j++) {
    array[j] = array[j + 1];
}

Alternatively, consider j = i + 1 to avoid boundary concerns:

for (int j = i + 1; j < size; j++) {
    array[j - 1] = array[j];
}

Variable Scope in Loops

Variables declared within for loop statement blocks cannot be used as global function variables.