Remove Element

• Difficulty: Easy
• Topics: Array, Two Pointers
• Link: https://leetcode.com/problems/remove-element/

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

Solution

1. Problem Deconstruction

Technical Definition: Given a mutable array nums of integers and an integer val, implement an in-place algorithm that removes all elements equal to val. The algorithm must partition the array such that the first k elements are all the values not equal to val, in any order. The function must return the integer k, which is the count of these elements. The algorithm must operate within the array’s original memory space without allocating a new array, leveraging the allowance of element reordering.

Beginner-Friendly Explanation: Imagine you have a list of numbers and a specific number you want to remove from that list. Your task is to physically shift all the numbers that are not the one you’re removing to the front of the list. You don’t care what order they end up in at the front. You also don’t care what is left in the back of the list after you’ve moved all the “good” numbers to the front. Your job is to count how many “good” numbers there are and make sure they are all at the start of the list.

Mathematical Formulation: Let $S$ be the sequence (array) nums of length $n$. Let $v$ be the integer val. Define the set of indices to keep as $K = \{ i \mid S[i] \neq v, \text{ for } 0 \leq i < n \}$. The goal is to compute the cardinality $k = |K|$ and to produce a permutation of the sequence $S'$ such that:

$$S'[0], S'[1], \ldots, S'[k-1] = \{ S[i] \mid i \in K \}$$

and the elements in the subsequence $S'[0..k-1]$ can be in any order. The operation must be performed with $O(1)$ auxiliary space.

Constraint Analysis:

• 0 <= nums.length <= 100: The upper bound of 100 is very small. This immediately suggests that even an algorithm with quadratic time complexity, $O(n^2)$, would be feasible (100² = 10,000 operations, which is negligible on modern hardware). It removes any performance pressure, allowing us to focus on correctness and conceptual understanding. The lower bound of 0 implies we must handle the empty array edge case.
• 0 <= nums[i] <= 50: The value range for array elements is limited and non-negative. This is not a significant constraint for the core algorithm logic but could be relevant if considering a non-comparison-based approach (though not necessary here). It assures us we won’t have to handle large numbers or negative numbers in the main logic.
• 0 <= val <= 100: The value to remove can be outside the range of nums[i] (e.g., val = 100 when no element exceeds 50). This is a crucial edge case. If val is not present in the array, the function must return the original array length and leave the array completely unchanged. This must be handled correctly.

2. Intuition Scaffolding

Analogies:

1. Real-World Metaphor (Filtering a Conveyor Belt): Imagine a conveyor belt (nums) carrying boxes of fruit. Some boxes are rotten (val). You have one worker at the start of the belt whose job is to take good boxes and put them on a shipping pallet at the very front of a warehouse. The worker doesn’t care about the order on the pallet. The worker can also look ahead on the conveyor belt. Every time they see a good box, they pick it up and walk it to the next available spot on the pallet. The rotten boxes are just let through and remain at the end of the warehouse. The number of good boxes on the pallet is k.
2. Gaming Analogy (Inventory Management): Think of your character’s inventory in a game (nums), which has limited slots. You need to remove all instances of a common, useless item (“Broken Sword” val) to make space for valuable loot. Instead of destroying them one by one, which is slow, you can quickly gather all the good items into the first few inventory slots. You can do this by scanning your inventory and swapping any good item you find with the first “Broken Sword” you left at the beginning of the inventory. The number of valuable items you keep is k.
3. Math Analogy (Partitioning a Set): This problem is a direct application of the Partition operation from algorithms like Quicksort. The goal is to partition the array into two segments: one where the predicate “element != val” is true, and one where it is false. The problem relaxes the requirement of ordering within the partitions, making it simpler than a full sort. It’s about grouping elements based on a binary condition.

Common Pitfalls:

1. Using Extra Space: The most common mistake is to create a new list/array to store the result, violating the in-place requirement. This is often a beginner’s first intuition.
2. Nested Loops and Shifting: A brute-force approach might involve finding an element val and then shifting all subsequent elements one to the left. This leads to an $O(n^2)$ algorithm which is inefficient for large n (though acceptable here due to constraints) and is more complex to implement correctly than the two-pointer approach.
3. Incorrect Pointer Management (Two-Pointer): When using the two-pointer technique, a common error is to increment the “write” pointer (k) before the swap, or to swap before checking the condition, which can lead to writing val into the valid front section.
4. Handling the “No val Present” Edge Case: Forgetting that if val is not in the array, the function should return n and not modify the array. An algorithm that always does a swap might incorrectly change the array’s order even when no removal is needed.
5. Off-by-One Errors: Misunderstanding whether the pointers are 0-indexed or 1-indexed, or whether the return value k is a count or an index, can lead to errors. For example, if the write pointer k is initialized to 0, it represents the next available index and the final value of k is the count.

3. Approach Encyclopedia

1. Brute Force (Shifting)

• What: This approach iterates through the array. Every time it finds val, it shifts all subsequent elements one place to the left to overwrite it. This requires a nested loop.
• Why: It’s a straightforward, intuitive method that performs the removal literally. It helps understand the problem’s requirement of “physical” removal by shifting.
• How (Pseudocode):

  function removeElement(nums, val):
      n = length(nums)
      i = 0
      while i < n:
          if nums[i] == val:
              // Shift all elements from i+1 to end left by 1
              for j from i+1 to n-1:
                  nums[j-1] = nums[j]
              n = n - 1  // Reduce the effective size of the array
          else:
              i = i + 1  // Only move forward if no shift occurred
      return n
  

• Complexity Proof:
  • Time Complexity: In the worst case, where all elements are val (e.g., nums = [1,1,1,1], val=1), the outer loop runs n times. For each of these iterations, the inner shift loop runs $(n-1) + (n-2) + ... + 1 = \frac{n(n-1)}{2}$ times. This is $O(n^2)$.
  • Space Complexity: Only a few integer variables (i, j, n) are used, independent of input size. This is $O(1)$.
• Visualization:
  nums = [0,1,2,2,3,0,4,2], val = 2

  i=0: [0,1,2,2,3,0,4,2] -> 0 !=2 -> i=1
  i=1: [0,1,2,2,3,0,4,2] -> 1 !=2 -> i=2
  i=2: [0,1,2,2,3,0,4,2] -> 2==2! SHIFT: [0,1,2,3,0,4,2,2] (n=7)
  i=2: [0,1,2,3,0,4,2,2] -> 2==2! SHIFT: [0,1,3,0,4,2,2,2] (n=6)
  i=2: [0,1,3,0,4,2,2,2] -> 3 !=2 -> i=3
  i=3: [0,1,3,0,4,2,2,2] -> 0 !=2 -> i=4
  i=4: [0,1,3,0,4,2,2,2] -> 4 !=2 -> i=5
  i=5: [0,1,3,0,4,2,2,2] -> 2==2! SHIFT: [0,1,3,0,4,2,2,2] (n=5)
  i=5: [0,1,3,0,4,2,2,2] -> 2==2! SHIFT: [0,1,3,0,4,2,2,2] (n=4)
  // Array is now [0,1,3,0,4, ...] and n=4 is returned. Incorrect! The element '2' at index 5 is still there.
  

  This reveals a flaw: the algorithm doesn’t re-check the current index i after a shift, which may have brought another val into that position. The correct pseudocode should not increment i after a shift.

2. Two-Pointer (Copy-Forward / Reader-Writer)

• What: This is the optimal approach. We use two pointers (indices), often called reader (or i) and writer (or k). The reader pointer scans every element in the original array. The writer pointer tracks the next position to place a valid (non-val) element. This efficiently builds the new array at the front.
• Why: It achieves the goal in a single pass, $O(n)$ time, with constant space $O(1)$. It is simple, efficient, and elegant.
• How (Pseudocode):

  function removeElement(nums, val):
      writer = 0                  // Initialize the writer pointer
      for reader in range(0, len(nums)):
          if nums[reader] != val:
              nums[writer] = nums[reader] // Copy the valid element forward
              writer = writer + 1         // Move the writer pointer forward
      return writer               // writer equals the count of valid elements
  

• Complexity Proof:
  • Time Complexity: The algorithm performs a constant-time check and a conditional copy operation for each of the n elements in the input array. This is $n \times O(1) = O(n)$.
  • Space Complexity: The algorithm uses only two integer variables (reader, writer). The space required does not scale with the input size $n$. This is $O(1)$.
• Visualization:
  nums = [0,1,2,2,3,0,4,2], val = 2 The writer pointer (k) marks the end of the valid partition.

  reader | writer | nums[reader] | Action              | nums array state
  -------|--------|--------------|---------------------|-------------------
    0    |   0    |      0 != 2  | copy, writer++      | [0,1,2,2,3,0,4,2]
    1    |   1    |      1 != 2  | copy, writer++      | [0,1,2,2,3,0,4,2]
    2    |   2    |      2 == 2  | skip                | [0,1,2,2,3,0,4,2]
    3    |   2    |      2 == 2  | skip                | [0,1,2,2,3,0,4,2]
    4    |   2    |      3 != 2  | copy, writer++      | [0,1,3,2,3,0,4,2]
    5    |   3    |      0 != 2  | copy, writer++      | [0,1,3,0,3,0,4,2]
    6    |   4    |      4 != 2  | copy, writer++      | [0,1,3,0,4,0,4,2]
    7    |   5    |      2 == 2  | skip                | [0,1,3,0,4,0,4,2]
  

  Loop ends. writer = 5 is returned. The first 5 elements [0,1,3,0,4] are the valid ones. The rest are unimportant.

4. Code Deep Dive

def removeElement(nums, val):
    k = 0  # 1. Writer pointer: Tracks the next available index for a valid element.
    # 2. Initializes the count of valid elements to 0. Also signifies the end of the valid partition.

    for i in range(len(nums)): # 3. Reader pointer: 'i' iterates over every element in the original array.
        if nums[i] != val:     # 4. Core check: Is the current element something we want to keep?
            nums[k] = nums[i]  # 5. Copy-Forward: Overwrite the next available slot in the valid partition with this good element.
            k += 1             # 6. Update Partition: Since we added a valid element, the end of the valid partition moves forward by one.
    # 7. Loop Termination: After processing all elements, 'i' has scanned the entire array.

    return k # 8. Result: 'k' now holds the number of valid elements, which is the size of the valid partition.

Edge Case Handling:

• Empty Input (nums = []): The for loop range(0) executes zero times. k remains 0 and is returned. This is correct.
• No Occurrences of val (e.g., nums = [1,2,3], val = 4): The condition nums[i] != val is always True. Every element is copied from index i to index k (which is the same as i in this case). The array remains [1,2,3] and k = 3 is returned. This meets the requirement of leaving the array unchanged when no removal is needed.
• All Occurrences of val (e.g., nums = [2,2,2], val = 2): The condition nums[i] != val is always False. The k pointer never increments. The loop ends, k = 0 is returned. The array’s first 0 elements are valid, which is correct. The contents of the array after the loop are technically [2,2,2], but since k=0, the judge will only check the first 0 elements, so the backend values are irrelevant.

5. Complexity War Room

Hardware-Aware Analysis: The Two-Pointer solution has excellent cache performance. It exhibits sequential reads (the for loop) and sequential writes (the nums[k] = ... assignment). This pattern is very friendly to the CPU’s cache prefetcher, minimizing cache misses. For the maximum constraint of n=100, the entire array fits comfortably in the L1 cache of any modern CPU (typically 32-64KB). The algorithm would execute in a few hundred CPU cycles at most.

Industry Comparison Table:

Approach	Time Complexity	Space Complexity	Readability	Interview Viability	Notes
Brute Force (Shifting)	$O(n^2)$	$O(1)$	Medium	❌ Poor	Conceptually simple but inefficient and tricky to implement correctly (off-by-one, re-checking).
Two-Pointer (Copy-Forward)	$O(n)$	$O(1)$	High	✅ Excellent	The standard, expected solution. Simple, efficient, and easy to explain.
Two-Pointer (Swap-and-Pop)	$O(n)$	$O(1)$	Medium	✅ Good	Useful if val is rare, as it reduces the number of writes. [0,1,2,2,3,0,4,2] -> [0,1,4,0,3, ...]

The Swap-and-Pop variant initializes a pointer n = len(nums) and iterates with i from 0 to < n. If nums[i] == val, it swaps nums[i] with nums[n-1] and decreases n--, then re-checks i. This is efficient if the elements to remove are few, as it avoids copying the latter part of the array. However, it does not preserve the original order of non-val elements, which is allowed.

6. Pro Mode Extras

Variants Section:

1. Remove Element (Stable Order): How would you solve this if you needed to maintain the relative order of the elements that are not removed? (Answer: The Copy-Forward two-pointer approach naturally achieves this, as it is a stable operation.)
2. Remove Duplicates from Sorted Array (LC 26): A direct extension of this pattern. The condition changes from if nums[i] != val to if nums[i] != nums[k-1] (checking for duplicates with the last valid element).
3. Move Zeroes (LC 283): This is essentially removeElement(nums, 0) but with an added requirement to set the remaining elements to zero? Actually, no. The requirement is to move all zeroes to the end while maintaining the relative order of non-zero elements. The solution is identical to the stable removeElement: use the two-pointer copy-forward for non-zeroes, then fill the remaining indices from k to the end with zeros.

   def moveZeroes(nums):
       k = 0
       for i in range(len(nums)):
           if nums[i] != 0:    # Copy non-zeroes forward
               nums[k] = nums[i]
               k += 1
       for i in range(k, len(nums)): # Fill the rest with zeros
           nums[i] = 0
   

Interview Cheat Sheet:

• First Clarification: Always state the time and space complexity of your solution first. For this problem, lead with “I can solve this in O(n) time and O(1) space using a two-pointer technique.”
• Whiteboard Draw: Draw the two pointers (reader/i and writer/k) on a sample array. Walk through the steps visually. This makes your logic undeniable.
• Mention Edge Cases: Explicitly list the edge cases you will handle: empty input, val not in nums, all elements are val.
• Code and Verify: After writing the code, test it verbally with the provided examples to catch any off-by-one errors.
• Discuss Alternatives: Even if you implement the optimal solution, briefly mentioning the brute-force approach shows you’ve considered the problem space thoroughly. You can then explain why it’s inferior.