Problem Description

You are given an integer array nums and an integer val. Your task is to remove all occurrences of val from the array in-place and return the count of elements that are not equal to val.

The problem requires you to modify the original array such that:

• The first k elements of nums contain all the elements that are not equal to val, where k is the count of such elements
• The order of these elements can be changed
• The remaining elements after position k don't matter

For example, if nums = [3, 2, 2, 3] and val = 3, after calling your function:

• The array should be modified to something like [2, 2, _, _] where _ represents any value
• The function should return 2 (since there are 2 elements not equal to 3)

The solution uses a two-pointer technique where we maintain a pointer k that tracks the position where the next non-val element should be placed. As we iterate through the array:

• When we encounter an element x that is not equal to val, we place it at position nums[k] and increment k
• When we encounter val, we simply skip it

This approach efficiently rearranges the array in a single pass with O(n) time complexity and O(1) space complexity, meeting the in-place requirement.

Intuition

The key insight is recognizing that we need to partition the array into two sections: elements we want to keep (not equal to val) and elements we want to remove (equal to val). Since we only care about the first k elements being the ones we keep, we don't need to actually "remove" elements - we just need to overwrite the array from the beginning with the valid elements.

Think of it like organizing a bookshelf: instead of physically removing unwanted books and shifting everything left (which would be expensive in terms of operations), we can simply pick out the books we want to keep and place them at the beginning of the shelf, one by one. The rest of the shelf doesn't matter.

This leads us to the two-pointer approach:

• One pointer (k) tracks where to place the next "good" element
• Another pointer (the loop variable) scans through all elements

When we find an element that's not val, we know it belongs in our "keep" section, so we place it at position k and move k forward. Elements equal to val are simply skipped over - they'll naturally end up being overwritten or left at the end of the array.

The beauty of this approach is that k automatically gives us the count of valid elements at the end, since it represents the next position to fill, which equals the number of elements we've already placed.

This way, we achieve the in-place modification with just one pass through the array, making it both time and space efficient.

Learn more about Two Pointers patterns.

Solution Approach

The solution implements a one-pass algorithm using a single pointer technique to solve the problem efficiently.

Algorithm Steps:

1. Initialize a counter: We start with k = 0, which serves dual purposes:

   • It acts as an index pointer for where to place the next valid element
   • It counts the number of elements not equal to val

2. Iterate through the array: We traverse each element x in nums:

   for x in nums:

3. Check and place valid elements: For each element x:

   • If x != val, it's a valid element we want to keep
   • We place it at position nums[k]
   • Increment k by 1 to move to the next available position

   if x != val:
       nums[k] = x
       k += 1

4. Return the count: After the loop completes, k represents the total number of valid elements, which we return.

Why this works:

• Elements from index 0 to k-1 will contain all elements not equal to val
• Elements from index k onwards are irrelevant (they might be old values or duplicates)
• The algorithm maintains the invariant that the first k positions always contain the valid elements we've processed so far

Time and Space Complexity:

• Time Complexity: O(n) where n is the length of the array, as we traverse the array exactly once
• Space Complexity: O(1) as we only use a constant amount of extra space (the variable k)

This approach is optimal because it achieves the required in-place modification with minimal operations - each element is read once and valid elements are written once.

Example Walkthrough

Let's walk through the solution with a concrete example to see how the algorithm works step by step.

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

We want to remove all occurrences of 2 from the array.

Initial Setup:

• k = 0 (pointer for next valid element placement)
• Array: [0, 1, 2, 2, 3, 0, 4, 2]

Step-by-step execution:

Iteration 1: x = 0 (index 0)

• 0 != 2, so it's valid
• Place at nums[0] = 0
• Increment k = 1
• Array: [0, 1, 2, 2, 3, 0, 4, 2] (no visible change)

Iteration 2: x = 1 (index 1)

• 1 != 2, so it's valid
• Place at nums[1] = 1
• Increment k = 2
• Array: [0, 1, 2, 2, 3, 0, 4, 2] (no visible change)

Iteration 3: x = 2 (index 2)

• 2 == 2, skip this element
• k remains 2
• Array: [0, 1, 2, 2, 3, 0, 4, 2]

Iteration 4: x = 2 (index 3)

• 2 == 2, skip this element
• k remains 2
• Array: [0, 1, 2, 2, 3, 0, 4, 2]

Iteration 5: x = 3 (index 4)

• 3 != 2, so it's valid
• Place at nums[2] = 3
• Increment k = 3
• Array: [0, 1, 3, 2, 3, 0, 4, 2] (overwrote first 2)

Iteration 6: x = 0 (index 5)

• 0 != 2, so it's valid
• Place at nums[3] = 0
• Increment k = 4
• Array: [0, 1, 3, 0, 3, 0, 4, 2] (overwrote second 2)

Iteration 7: x = 4 (index 6)

• 4 != 2, so it's valid
• Place at nums[4] = 4
• Increment k = 5
• Array: [0, 1, 3, 0, 4, 0, 4, 2]

Iteration 8: x = 2 (index 7)

• 2 == 2, skip this element
• k remains 5
• Array: [0, 1, 3, 0, 4, 0, 4, 2]

Final Result:

• Return value: k = 5 (there are 5 elements not equal to 2)
• Modified array: [0, 1, 3, 0, 4, ?, ?, ?] where ? represents values we don't care about
• The first 5 elements [0, 1, 3, 0, 4] are all the elements from the original array that weren't equal to 2

The algorithm successfully partitioned the array so that all non-val elements are at the beginning, and it correctly returns the count of such elements.

Solution Implementation

Time and Space Complexity

The time complexity is O(n) where n is the length of the array nums. This is because the algorithm iterates through the entire array exactly once with a single for loop, performing constant-time operations (comparison and assignment) for each element.

The space complexity is O(1) as the algorithm only uses a single extra variable k to track the position for placing non-target elements. The modifications are done in-place within the original array without allocating any additional data structures that scale with the input size.

Learn more about how to find time and space complexity quickly.

Common Pitfalls

1. Attempting to Delete Elements While Iterating

A common mistake is trying to use Python's del or remove() methods while iterating through the array:

Incorrect Approach:

def removeElement(self, nums: List[int], val: int) -> int:
    for i in range(len(nums)):
        if nums[i] == val:
            del nums[i]  # This causes index shifting issues!
    return len(nums)

Why it fails: Deleting elements shifts all subsequent elements left, causing index misalignment and potentially skipping elements or going out of bounds.

Solution: Use the two-pointer technique as shown in the correct solution, which overwrites values without deletion.

2. Creating a New Array Instead of Modifying In-Place

Some might create a new array with valid elements:

Incorrect Approach:

def removeElement(self, nums: List[int], val: int) -> int:
    new_nums = [x for x in nums if x != val]
    nums = new_nums  # This doesn't modify the original array!
    return len(new_nums)

Why it fails: Assigning nums = new_nums only changes the local reference, not the original array passed to the function.

Solution: Modify the array elements directly using index assignment: nums[k] = x

3. Misunderstanding the Return Value

Some might think they need to return the modified array:

Incorrect Approach:

def removeElement(self, nums: List[int], val: int) -> int:
    k = 0
    for x in nums:
        if x != val:
            nums[k] = x
            k += 1
    return nums[:k]  # Returning array instead of count!

Why it fails: The problem requires returning an integer count, not the array itself.

Solution: Return k (the count) while ensuring the array is modified in-place.

4. Off-by-One Errors with the Counter

Incrementing the counter incorrectly:

Incorrect Approach:

def removeElement(self, nums: List[int], val: int) -> int:
    k = 1  # Starting from 1 instead of 0
    for x in nums:
        if x != val:
            nums[k] = x
            k += 1
    return k

Why it fails: Starting k at 1 skips the first position (index 0), leading to incorrect array modification.

Solution: Always initialize k = 0 to start placing valid elements from the beginning of the array.