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 elements beyond the first k elements are not important as well as the size of nums.
  • Return k.

Examples

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 being 0, 1, 3, 0, and 4.
Note that the five elements can be returned in any order, and it does not matter what you leave beyond the returned k.

Constraints

  • 0 <= nums.length <= 100
  • 0 <= nums[i] <= 50
  • 0 <= val <= 100

Thinking Process

  1. Two Pointers Pattern: Classic pattern for in-place array modification
  • Two indices move toward each other or in the same direction.
  • Works on sorted arrays or when in-place modification is required.
  • Loop invariant: all indices outside [left, right] are already resolved.
Two pointers 1 3 5 7 9 L R move L/R based on comparison

Common Approaches

Typical techniques for this pattern:

Approach Time Space Notes
Opposite ends (this problem) O(n) O(1) Sorted array pair search, reversal
Slow / fast pointers O(n) O(1) Linked list middle, cycle detection
Same-direction chase O(n) O(1) Remove duplicates in-place
Sliding window (variable) O(n) O(1) Subarray with constraint

Solution

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int last = 0;
        for(int curr = 0; curr < (int)nums.size(); curr++) {
            if(nums[curr] != val) {
                nums[last] = nums[curr];
                last += 1;
            }
        }
        return last;
    }
};

Solution Explanation

Approach: Opposite ends (this problem)

Key idea: 1. Two Pointers Pattern: Classic pattern for in-place array modification

How the code works:

  1. Two Pointers Pattern: Classic pattern for in-place array modification
    • Two indices move toward each other or in the same direction.
    • Works on sorted arrays or when in-place modification is required.
    • Loop invariant: all indices outside [left, right] are already resolved.

Walkthrough — input nums = [3,2,2,3], val = 3, expected output 2, nums = [2,2,_,_]:

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).

Common Mistakes

  1. Empty array: nums = [] → return 0
  2. All elements removed: nums = [3,3,3], val = 3 → return 0
  3. No elements removed: nums = [1,2,3], val = 4 → return 3
  4. Single element removed: nums = [1], val = 1 → return 0

  5. Single element kept: nums = [1], val = 2 → return 1

  6. Wrong pointer logic: Incrementing last even when element equals val
  7. Index out of bounds: Not checking bounds when accessing nums[curr]
  8. Wrong return value: Returning nums.size() instead of last
  9. Not modifying array: Only counting without actually removing elements
  10. Type casting: Forgetting (int) cast for nums.size() comparison

Key Takeaways

  1. Two Pointers Pattern: Classic pattern for in-place array modification
  2. Write Pointer (last): Tracks where to write next valid element
  3. Read Pointer (curr): Scans through all elements
  4. In-Place: No extra space needed, modifies array directly
  5. Order Preservation: Maintains relative order of non-removed elements

References

Template Reference