Skip to main content

Two Pointer

Remove Element Solution In C++/Java/Python/JS

Problem Description

Given an integer array nums and an integer val, remove all occurrences of val in nums in-place. The order of the elements may be changed. Then return the number of elements in nums which are not equal to val.
Consider the number of elements in nums which are not equal to val be k, to get accepted, you need to do the following things:
- Change the array nums such that the first k elements of nums contain the elements which are not equal to val. The remaining elements of nums are not important as well as the size of nums.
- Return k.

Custom Judge:

The judge will test your solution with the following code:

int[] nums = [...]; // Input array
int val = ...; // Value to remove
int[] expectedNums = [...]; // The expected answer with correct length.
                            // It is sorted with no values equaling val.

int k = removeElement(nums, val); // Calls your implementation

assert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < actualLength; i++) {
    assert nums[i] == expectedNums[i];
}

If all assertions pass, then your solution will be accepted.

Example 1:

Input: nums = [3,2,2,3], val = 3
Output: 2, nums = [2,2,_,_]
Explanation: Your function should return k = 2, with the first two elements of nums being 2.
It does not matter what you leave beyond the returned k (hence they are underscores).

Example 2:

Input: nums = [0,1,2,2,3,0,4,2], val = 2
Output: 5, nums = [0,1,4,0,3,_,_,_]
Explanation: Your function should return k = 5, with the first five elements of nums containing 0, 0, 1, 3, and 4.
Note that the five elements can be returned in any order.
It does not matter what you leave beyond the returned k (hence they are underscores).

Constraints:

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100
💡
Try it Yourself First
Use two pointers—one to scan, one to place valid elements—to remove unwanted values in-place efficiently. Simple and fast!. Let’s explore!

Two Pointer Approach

Intuition

Our objective is to remove all occurrences of a specific value from an array, modifying it in-place, and return the count of remaining valid elements. Since we're allowed to ignore elements beyond the new length and don't need to maintain the full array structure, we can solve this problem efficiently with a two pointer strategy.
The main idea is to think of the array like a space where we can overwrite values as we go. Our goal is to keep all the numbers that are not equal to the given value and remove the ones that are.
To do this, we use a pointer k that tells us where to place the next number that we want to keep. We go through the array from start to end. Every time we find a number that is not equal to the value we want to remove, we put it at index k and move k one step forward.
If we find a number that is equal to the value to be removed, we just skip it and do nothing.
By the end, the first k elements of the array will be all the numbers we kept, and the rest of the array can be ignored. This way, we remove the unwanted values without using extra space and without worrying about the order.

Approach

Step 1: Initialize a Placement Pointer
We start by creating a pointer k (an index variable) which will keep track of the position where the next valid (non-target) element should be placed. Initially, k = 0, meaning we’re ready to place the first valid number at the beginning of the array.

Step 2: Traverse the Array
We loop through each element in the array using a normal for loop. For each element at index i, we check if it is not equal to the target value val that we want to remove.

Step 3: Overwrite with Valid Elements
If the current element is not equal to val, we copy it to index k. This effectively pushes valid elements forward in the array. After placing the element, we increase k by 1 so that the next valid element goes to the next position.

Step 4: Skip Unwanted Elements
If the current element is equal to val, we do nothing and just move to the next element. This skips over all occurrences of the value we want to remove.

Step 5: Return Count of Valid Elements
Once the loop finishes, the first k elements in the array contain all the values that are not equal to val. The rest of the array can be ignored. We return k as the count of valid elements.

Dry Run

Input: nums = [3, 2, 2, 3], val = 3
Initialize:
k = 0 (Pointer to place the next valid element)
Start Loop:
Iteration 1 (i = 0, nums[i] = 3):
nums[i] == val → skip this element
Iteration 2 (i = 1, nums[i] = 2):
nums[i] != val → write nums[k] = nums[i] → nums[0] = 2
Increment k → k = 1
nums is now: [2, 2, 2, 3]
Iteration 3 (i = 2, nums[i] = 2):
nums[i] != val → write nums[k] = nums[i] → nums[1] = 2
Increment k → k = 2
nums is now: [2, 2, 2, 3]
Iteration 4 (i = 3, nums[i] = 3):
nums[i] == val → skip this element
Final State:
k = 2 (Number of valid elements)
Modified nums: [2, 2, _, _] ← only first k elements matter
Output:
Return k = 2
Valid portion of array: [2, 2]

Code for All Languages
C++ 
// Approach: Two pointer approach to Remove Element
// Language: C++

class Solution {
public:
    // This function removes all instances of a given value `val` from the input
    // vector `nums` in-place, and returns the number of elements left after removal.
    // The order of remaining elements does not matter.
    int removeElement(vector<int>& nums, int val) {
        // Step 1: Initialize a pointer `k` to mark the next valid position
        int k = 0;

        // Step 2: Iterate over all elements in the array
        for (int i = 0; i < nums.size(); i++) {
            // Step 3: If current element is not equal to `val`,
            // write it to the current `k` position and increment `k`
            if (nums[i] != val) {
                nums[k] = nums[i];
                k++;
            }
            // If nums[i] == val, do nothing — skip this element
        }

        // Step 4: Return the count of valid elements remaining after removal
        return k;
    }
};

Java 
// Approach: Two pointer approach to Remove Element
// Language: Java

class Solution {
    // This function removes all instances of the given value `val` from the input
    // array `nums` in-place, and returns the number of elements left after removal.
    // The order of the remaining elements does not matter.
    public int removeElement(int[] nums, int val) {
        // Step 1: Initialize a pointer `k` to mark the next valid position
        int k = 0;

        // Step 2: Iterate over all elements in the array
        for (int i = 0; i < nums.length; i++) {
            // Step 3: If current element is not equal to `val`,
            // write it to the current `k` position and increment `k`
            if (nums[i] != val) {
                nums[k] = nums[i];
                k++;
            }
            // If nums[i] == val, we skip this element
        }

        // Step 4: Return the count of valid elements remaining after removal
        return k;
    }
}

Python 
# Approach: Two pointer approach to Remove Element
# Language: Python

class Solution(object):
    def removeElement(self, nums, val):
        """
        This function removes all instances of the given value `val` from the input
        list `nums` in-place, and returns the number of elements left after removal.
        The order of the remaining elements does not matter.

        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        # Step 1: Initialize a pointer `k` to mark the next valid position
        k = 0

        # Step 2: Iterate over all elements in the array
        for i in range(len(nums)):
            # Step 3: If current element is not equal to `val`,
            # write it to the current `k` position and increment `k`
            if nums[i] != val:
                nums[k] = nums[i]
                k += 1
            # If nums[i] == val, we skip this element

        # Step 4: Return the count of valid elements remaining after removal
        return k

Javascript 
// Approach: Two pointer approach to Remove Element
// Language: JavaScript

/**
 * This function removes all instances of the given value `val` from the input
 * array `nums` in-place, and returns the number of elements left after removal.
 * The order of the remaining elements does not matter.
 * 
 * @param {number[]} nums - The input array
 * @param {number} val - The value to remove
 * @return {number} The number of valid elements remaining
 */
var removeElement = function(nums, val) {
    // Step 1: Initialize a pointer `k` to mark the next valid position
    let k = 0;

    // Step 2: Iterate over all elements in the array
    for (let i = 0; i < nums.length; i++) {
        // Step 3: If current element is not equal to `val`,
        // write it to the current `k` position and increment `k`
        if (nums[i] !== val) {
            nums[k] = nums[i];
            k++;
        }
        // If nums[i] == val, we skip this element
    }

    // Step 4: Return the count of valid elements remaining after removal
    return k;
};

Time Complexity: O(n)

  • Array Traversal
    – We traverse the entire array once using a single for loop.
    – For each element, we perform a constant-time check and possibly a constant-time assignment.
    – This step takes O(n) time, where n is the size of the array.
  • Final Operations
     – At the end, we return the value of k, which is a constant-time operation.
    – The positions beyond k are left unchanged, as per the problem's instruction, so no extra clean-up is needed.
  • Overall Time Complexity
    Total is O(n), Where n is the number of elements in the input array.

Space Complexity: O(1)

  • Auxiliary Space Complexity: O(1)
    – This approach uses a single integer variable k to track the next valid position.
    – No extra data structures like maps, sets, or vectors are used.
    – All operations are performed in-place, modifying the input array directly.
    – The loop and index variables (i, k) use only constant space.
  • Total Space Complexity
    – Input array nums is modified in-place and no additional array or buffer is created.
    – Therefore, we only use a constant amount of extra space, regardless of the input size.
  • Final space complexity: O(1)
This problem can be effectively solved using the two-pointer technique to remove elements in-place without extra space. Alternatively, many programming languages provide built-in functions that simplify this process. For example, C++ offers the std::remove algorithm, which works by shifting all elements not equal to the target value toward the front of the container, effectively “removing” the unwanted elements. It returns an iterator pointing to the new end of the valid range, allowing the remaining elements to be ignored or erased. This built-in algorithm internally uses a similar two-pointer approach, ensuring efficient in-place modification. Understanding both the manual two-pointer method and the built-in std::remove algorithm provides a comprehensive view of how array element removal can be optimized.
int removeElement(vector<int>& nums, int val) {
    // std::remove shifts all elements not equal to val to the front
    // and returns an iterator to the new logical end.
    auto new_end = std::remove(nums.begin(), nums.end(), val);
    // The number of valid elements is the distance from begin to new_end
    return std::distance(nums.begin(), new_end);
}

Learning Tip

Now we have successfully tackled this problem, let’s try these similar problems.

Remove Duplicates from Sorted Array

Given an integer array nums sorted in non-decreasing order, remove the duplicates in-place such that each unique element appears only once. The relative order of the elements should be kept the same. Then return the number of unique elements in nums.

Remove Linked List Elements

Given the head of a linked list and an integer val, remove all the nodes of the linked list that has Node.val == val, and return the new head.