Remove Element

Easy

ArrayTwo Pointers

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 to 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
int k = removeElement(nums, val); // Calls your implementationassert k == expectedNums.length;
sort(nums, 0, k); // Sort the first k elements of nums
for (int i = 0; i < k; i++) {
    assert nums[i] == expectedNums[i];
}

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

Solution Approaches

Approach 1: Two Pointers (Slow-Fast)

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

The simplest approach uses two pointers: a slow pointer that tracks where to place the next valid element, and a fast pointer that scans through the array.

Intuition:

- We want to collect all elements that are NOT equal to val - We can overwrite the array in-place as we go - No need to preserve order or worry about elements beyond index k

Algorithm: 1. Initialize k = 0 (write position for next valid element) 2. Loop through array with pointer i: - If nums[i] !== val: it's a valid element - Copy it to position k: nums[k] = nums[i] - Increment k - If nums[i] === val: skip it (don't increment k) 3. Return k (count of valid elements)

Example Trace: nums = [3,2,2,3], val = 3 - i=0: nums[0]=3, equals val → skip - i=1: nums[1]=2, not equal → nums[0]=2, k=1 - i=2: nums[2]=2, not equal → nums[1]=2, k=2 - i=3: nums[3]=3, equals val → skip - Return k=2, array: [2,2,_,_]

Solution Code

function removeElement(nums: number[], val: number): number {
  let k = 0; // Write pointer

  for (let i = 0; i < nums.length; i++) {
    // If current element is not the target value
    if (nums[i] !== val) {
      // Place it at position k
      nums[k] = nums[i];
      k++;
    }
    // Otherwise skip (don't increment k)
  }

  return k;
}

Visualization: RemoveElementTwoPointerViz(Component registered but not yet implemented)

Approach 2: Two Pointers (Optimized for Few Removals)

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

When elements to remove are rare, we can optimize by swapping with elements from the end of the array instead of shifting all elements.

Intuition:

- If val appears rarely, the first approach does many unnecessary copies - Instead of copying every valid element, only swap elements equal to val with elements from the end - This reduces the number of assignment operations when few elements match val

Algorithm: 1. Initialize two pointers: left = 0, right = nums.length - 1 2. While left <= right: - If nums[left] === val: - Swap with element at right: nums[left] = nums[right] - Shrink from right: right-- - Don't increment left (need to check swapped element) - Else: - This element is valid, move to next: left++ 3. Return left (all valid elements are before this index)

Example Trace: nums = [3,2,2,3], val = 3 - left=0, right=3: nums[0]=3 equals val → swap with nums[3], right=2 - Array: [3,2,2,3] (swapped 3 with 3) - left=0, right=2: nums[0]=3 equals val → swap with nums[2], right=1 - Array: [2,2,2,3] - left=0, right=1: nums[0]=2 not equal → left=1 - left=1, right=1: nums[1]=2 not equal → left=2 - left=2 > right=1 → stop - Return left=2, array: [2,2,_,_]

When to Use: - When elements to remove are rare (few matches) - When assignment operations are expensive - When you want to minimize writes to the array

Solution Code

function removeElement(nums: number[], val: number): number {
  let left = 0;
  let right = nums.length - 1;

  while (left <= right) {
    if (nums[left] === val) {
      // Found element to remove - swap with element from end
      nums[left] = nums[right];
      right--; // Shrink the valid range
      // Don't increment left - need to check the swapped element
    } else {
      // Valid element - move to next
      left++;
    }
  }

  // All elements before 'left' are valid (not equal to val)
  return left;
}

Visualization: RemoveElementSwapViz(Component registered but not yet implemented)

Comparison: When to Use Each Approach

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

Both approaches solve the problem with O(n) time and O(1) space, but they have different performance characteristics in practice.

Approach 1 (Copy Forward):

- Pros: - Simple and intuitive - Preserves relative order of remaining elements - Predictable number of operations (exactly n iterations) - Cons: - Performs copies even when element doesn't need to be removed - May do unnecessary work when most elements are valid - Best for: - When val appears frequently - When order preservation is desired (though not required) - When simplicity and readability are priorities

Approach 2 (Swap from End): - Pros: - Fewer assignment operations when val is rare - More efficient when elements to remove are sparse - Avoids copying valid elements unnecessarily - Cons: - Slightly more complex logic - Does not preserve relative order - May swap multiple times near boundaries - Best for: - When val appears rarely - When minimizing write operations matters - When order doesn't matter (which it doesn't per problem)

Benchmark Example: For nums = [1,2,3,4,5,6,7,8,9,10], val = 1 (only 1 match): - Approach 1: 10 reads, 9 writes (copies all valid elements) - Approach 2: 10 reads, 1 write (only swaps the matched element)

For nums = [1,1,1,1,1,1,1,1,1,1], val = 1 (all match): - Approach 1: 10 reads, 0 writes (no valid elements to copy) - Approach 2: 10 reads, 5 writes (swaps pairs from ends)

Conclusion: In an interview, demonstrate knowledge of both approaches and explain the trade-offs. Approach 1 is usually preferred for its simplicity unless there's a specific reason to optimize for fewer writes.

Solution Code

// Side-by-side comparison

// Approach 1: Copy forward (simpler)
function removeElement1(nums: number[], val: number): number {
  let k = 0;
  for (let i = 0; i < nums.length; i++) {
    if (nums[i] !== val) {
      nums[k++] = nums[i];
    }
  }
  return k;
}

// Approach 2: Swap from end (optimized for rare removals)
function removeElement2(nums: number[], val: number): number {
  let left = 0, right = nums.length - 1;
  while (left <= right) {
    if (nums[left] === val) {
      nums[left] = nums[right--];
    } else {
      left++;
    }
  }
  return left;
}

// Both are O(n) time, O(1) space
// Choose based on: frequency of val, need for order, write cost

Visualization: RemoveElementComparisonViz(Component registered but not yet implemented)