Remove Element

Given an array nums and a value val, remove all instances of that value in-place and return the new length of the array. Do not allocate extra space for another array. Modify the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn’t matter what you leave beyond the new length.

Sample Input and Expected Output:

Input:

nums = [3, 2, 2, 3], val = 3

Output:

Length after removing elements with value 3: 2 // The array becomes [2, 2]

Input:

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

Output:

Length after removing elements with value 2: 5 // The array becomes [0, 1, 3, 0, 4]

Remove Element Solution in C++:

The idea is to use a two-pointer approach. We use one pointer (i) to iterate through the array and another pointer (j) to keep track of the position where we need to insert non-val elements. When we encounter a non-val element at position i, we place it at the position pointed by j and increment both i and j. The final value of j will give us the new length of the array after removing elements with value val.

#include <iostream>
#include <vector>

int removeElement(std::vector<int>& nums, int val) {
    int j = 0; // Pointer to track the position to insert non-val elements.

    for (int i = 0; i < nums.size(); i++) {
        if (nums[i] != val) {
            nums[j] = nums[i]; // Place the non-val element at the new position.
            j++; // Move j to the next position.
        }
    }

    return j; // Length of the array after removing elements with value val.
}

int main() {
    std::vector<int> nums1 = {3, 2, 2, 3};
    std::vector<int> nums2 = {0, 1, 2, 2, 3, 0, 4, 2};
    int val1 = 3;
    int val2 = 2;

    int length1 = removeElement(nums1, val1);
    int length2 = removeElement(nums2, val2);

    std::cout << "Length after removing elements with value " << val1 << ": " << length1 << std::endl;
    std::cout << "Length after removing elements with value " << val2 << ": " << length2 << std::endl;

    return 0;
}

Time Complexity and Space Complexity:

The time complexity of the solution is O(n), where n is the size of the input vector nums. This is because we use a two-pointer approach that traverses the array once.

The space complexity is O(1) as we are using a constant amount of additional space for variables in the solution, regardless of the size of the input array. The removal of elements is performed in-place, modifying the original array.