Skip to main content
CodePeetCodePeet
CodePeet 250

Remove Element

EASYProblemSolveExternal Links

Description

Given an integer array nums and an integer val, remove all occurrences of val from nums in-place. The relative order of the elements that are not equal to val may change. Then return the number of elements in nums which are not equal to val.

More specifically, if k is the count of elements not equal to val, you must ensure that the first k positions of nums contain exactly those elements. The values beyond index k - 1 do not matter.

You are not allowed to use extra space for another array — you must modify the input array directly using only O(1) extra memory.

Examples

Example 1

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

Output: 2, nums = [2, 2, _, _]

Explanation: The value 3 appears at indices 0 and 3. After removal, the two elements that are not equal to 3 are both 2. They are placed at the beginning of the array. The underscores represent positions whose values no longer matter. The function returns k = 2.

Example 2

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

Output: 5, nums = [0, 1, 3, 0, 4, _, _, _]

Explanation: The value 2 appears at indices 2, 3, and 7. The five elements that are not 2 are 0, 1, 3, 0, and 4. These are placed in the first five positions (in any order). The function returns k = 5.

Example 3

Input: nums = [1], val = 1

Output: 0, nums = [_]

Explanation: The only element equals val, so every element is removed. The function returns k = 0, and nothing in the array matters.

Constraints

  • 0 ≤ nums.length ≤ 100
  • 0 ≤ nums[i] ≤ 50
  • 0 ≤ val ≤ 100

Editorial

Brute Force

Intuition

The most straightforward way to think about this problem is: whenever you find an element equal to val, shift every element after it one position to the left to fill the gap, and reduce the effective size of the array by one.

Imagine you have a line of people standing shoulder to shoulder. If you need to remove someone from the middle of the line, everyone behind that person must shuffle one step forward to close the gap. This is exactly what the brute force does — for every occurrence of val, it shifts the entire remaining portion of the array to the left.

This shifting is expensive because each removal forces us to move potentially many elements. If there are many copies of val spread throughout the array, we end up doing a lot of redundant shifting work.

Step-by-Step Explanation

Let's trace through with nums = [3, 2, 2, 3], val = 3:

Step 1: Start scanning from index 0. The effective length is 4.

Step 2: Check nums[0] = 3. It equals val. We need to remove it by shifting all elements after index 0 one position to the left.

  • Shift: nums[1]=2 moves to nums[0], nums[2]=2 moves to nums[1], nums[3]=3 moves to nums[2].
  • Array becomes [2, 2, 3, 3]. Effective length decreases to 3.
  • Since we shifted, we do NOT advance our scan index — the new nums[0] hasn't been checked yet.

Step 3: Check nums[0] = 2. It does NOT equal val (3). No action needed. Move to index 1.

Step 4: Check nums[1] = 2. It does NOT equal val. Move to index 2.

Step 5: Check nums[2] = 3. It equals val. Shift all elements after index 2 left. But index 2 is the last position in our effective range, so there is nothing to shift. Effective length decreases to 2.

Step 6: Scanning index is now past the effective length. Return k = 2.

Brute Force — Shift Elements on Every Removal — Watch how each time we encounter val, the entire remaining array shifts left to fill the gap, making this approach costly for large arrays.

Algorithm

  1. Initialize an effective length variable to the array size.
  2. Start a scan index i at 0.
  3. While i is less than the effective length:
    a. If nums[i] equals val:
    • Shift all elements from i+1 to effective_length-1 one position to the left.
    • Decrease the effective length by 1.
    • Do NOT increment i (the new element at i needs checking).
      b. If nums[i] does not equal val:
    • Increment i.
  4. Return the effective length as k.

Code

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int n = nums.size();
        int i = 0;
        while (i < n) {
            if (nums[i] == val) {
                // Shift all elements after i one position left
                for (int j = i; j < n - 1; j++) {
                    nums[j] = nums[j + 1];
                }
                n--; // Reduce effective size
            } else {
                i++;
            }
        }
        return n;
    }
};
class Solution:
    def removeElement(self, nums: list[int], val: int) -> int:
        n = len(nums)
        i = 0
        while i < n:
            if nums[i] == val:
                # Shift all elements after i one position left
                for j in range(i, n - 1):
                    nums[j] = nums[j + 1]
                n -= 1  # Reduce effective size
            else:
                i += 1
        return n
class Solution {
    public int removeElement(int[] nums, int val) {
        int n = nums.length;
        int i = 0;
        while (i < n) {
            if (nums[i] == val) {
                // Shift all elements after i one position left
                for (int j = i; j < n - 1; j++) {
                    nums[j] = nums[j + 1];
                }
                n--; // Reduce effective size
            } else {
                i++;
            }
        }
        return n;
    }
}

Complexity Analysis

Time Complexity: O(n²)

In the worst case, every element equals val. For each of the n elements, we shift the remaining array left, which takes O(n) time per shift. This gives us n × O(n) = O(n²) total operations.

Even in the average case, each removal triggers a shift of the remaining elements, making this approach quadratic.

Space Complexity: O(1)

We only use a few integer variables (i, j, n). No additional data structures are allocated, so space usage is constant.

Why This Approach Is Not Efficient

The brute force approach has O(n²) time complexity because every removal triggers a left-shift of all subsequent elements. With n up to 100, this means up to 100 × 100 = 10,000 operations — manageable for this constraint, but the approach is fundamentally wasteful.

The core inefficiency is that we are doing unnecessary work: when we shift elements left to fill a gap, we are moving elements that might themselves get removed later. We are also maintaining the relative order of elements, but the problem explicitly says the order of elements may change.

Key insight: instead of shifting elements to fill gaps (which costs O(n) per removal), what if we simply placed non-val elements at the front of the array as we encounter them? This way, each element is processed exactly once, reducing the total work from O(n²) to O(n).

Optimal Approach - Two Pointers (Overwrite)

Intuition

Instead of removing elements by shifting, we can use a much simpler idea: keep a write pointer k that tracks where the next "good" element should go. As we scan through the array with a read pointer, every time we see an element that is NOT equal to val, we copy it to position k and advance k.

Think of it like a teacher collecting homework papers. The teacher walks past every desk (the read pointer). If a student has completed their work (element ≠ val), the teacher takes the paper and stacks it on a growing pile (writes it at position k). If a student hasn't done the work (element == val), the teacher simply moves on. At the end, the pile height (k) tells exactly how many completed papers there are.

The beauty is that the write pointer k is always at or behind the read pointer, so we never overwrite an element we haven't yet read. Every element is read exactly once and written at most once, making this a single-pass O(n) solution.

Step-by-Step Explanation

Let's trace through with nums = [0, 1, 2, 2, 3, 0, 4, 2], val = 2:

Step 1: Initialize write pointer k = 0. Start scanning from index 0.

Step 2: Read nums[0] = 0. Is 0 == 2? No. Copy 0 to nums[k=0]. Increment k to 1.

  • Array: [0, 1, 2, 2, 3, 0, 4, 2] (no visible change since nums[0] was already 0).

Step 3: Read nums[1] = 1. Is 1 == 2? No. Copy 1 to nums[k=1]. Increment k to 2.

  • Array: [0, 1, 2, 2, 3, 0, 4, 2] (no visible change).

Step 4: Read nums[2] = 2. Is 2 == 2? Yes. Skip this element. k stays at 2.

Step 5: Read nums[3] = 2. Is 2 == 2? Yes. Skip again. k stays at 2.

Step 6: Read nums[4] = 3. Is 3 == 2? No. Copy 3 to nums[k=2]. Increment k to 3.

  • Array: [0, 1, 3, 2, 3, 0, 4, 2] (overwrote the first 2).

Step 7: Read nums[5] = 0. Is 0 == 2? No. Copy 0 to nums[k=3]. Increment k to 4.

  • Array: [0, 1, 3, 0, 3, 0, 4, 2] (overwrote the second 2).

Step 8: Read nums[6] = 4. Is 4 == 2? No. Copy 4 to nums[k=4]. Increment k to 5.

  • Array: [0, 1, 3, 0, 4, 0, 4, 2].

Step 9: Read nums[7] = 2. Is 2 == 2? Yes. Skip. k stays at 5.

Step 10: Scan complete. Return k = 5. First 5 elements: [0, 1, 3, 0, 4].

Two Pointers — Overwriting Non-Val Elements Forward — Watch how the write pointer k only advances when we find a non-val element, efficiently collecting all valid elements at the front of the array in a single pass.

Algorithm

  1. Initialize a write pointer k = 0.
  2. For each element nums[i] in the array (i from 0 to n-1):
    a. If nums[i] ≠ val:
    • Copy nums[i] to nums[k].
    • Increment k.
      b. If nums[i] == val:
    • Do nothing (skip it).
  3. Return k.

Code

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int k = 0;
        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != val) {
                nums[k] = nums[i];
                k++;
            }
        }
        return k;
    }
};
class Solution:
    def removeElement(self, nums: list[int], val: int) -> int:
        k = 0
        for i in range(len(nums)):
            if nums[i] != val:
                nums[k] = nums[i]
                k += 1
        return k
class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0;
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[k] = nums[i];
                k++;
            }
        }
        return k;
    }
}

Complexity Analysis

Time Complexity: O(n)

We traverse the array exactly once with the read pointer i. Each element is read once and at most written once (to position k). Both the comparison and the copy are O(1) operations, giving us n iterations × O(1) work = O(n) total.

This is optimal because we must inspect every element at least once to determine whether it equals val.

Space Complexity: O(1)

We use only two integer variables (i and k). The modification is done in-place within the original array, so no additional memory scales with input size.