💬 Discord
Sign In
NeetCode #42LC-27EasyArrays & HashingNC 250
← Back to All Problems

#42 · #27 · Remove Element(移除元素)

📌 Problem Statement & Constraints

Given an integer array nums and an integer val, remove all occurrences of val in place. The order of the remaining elements may change. Return k, the number of elements not equal to val; the first k slots of nums must hold those elements. Constraints: 0 <= nums.length <= 100, 0 <= nums[i], val <= 50.

💡 Core Algorithmic Approaches

  1. The problem allows O(1) extra memory and does not require preserving order, which invites a single write pointer.
  2. Maintain k, the length of the kept prefix. Scan nums with a read pointer i.
  3. Whenever nums[i] != val, copy it to nums[k] and increment k. The write pointer never overtakes the read pointer, so no data is lost.
  4. Return k at the end. The bytes beyond k are irrelevant to the judge.

💻 Benchmark Python3 Implementation

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        k = 0                       # length of the kept prefix
        for i in range(len(nums)):
            if nums[i] != val:
                nums[k] = nums[i]   # write pointer never overtakes read pointer
                k += 1
        return k


# Swap-based variant that explicitly exploits "order may change"
class Solution2:
    def removeElement(self, nums: List[int], val: int) -> int:
        n = len(nums)
        i = 0
        while i < n:
            if nums[i] == val:
                n -= 1
                nums[i] = nums[n]   # move the last element into the hole
            else:
                i += 1
        return n

⚡ Complexity Deep Dive

⏱️ Time Complexity
O(n): each element is read once. The swap variant is also O(n) but performs fewer writes when val is rare.
💾 Space Complexity
O(1) extra space -- the compaction happens inside nums itself.

⚠️ Interview Pitfalls & Follow-ups

  • Using nums.remove(val) in a loop: each call is O(n) and shifts elements, giving O(n^2), and the loop indices become wrong as the list shrinks.
  • Building a new list and returning its length: the problem requires the compaction to happen in nums.
  • Thinking order must be preserved: the statement explicitly allows reordering, which is what makes the O(n)-writes swap variant legal. (If order were required, use the write-pointer version instead.)
  • Returning the compacted list instead of k: the signature returns an integer; the judge reads the first k slots of nums.