Remove Element

Problem Statement

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.

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

Approach 1: Two Pointers

Explanation

We can use two pointers to solve this problem efficiently:

  1. Initialize two pointers: k at the beginning of the array and i to iterate through the array.
  2. Iterate through the array with i.
  3. If the current element is not equal to val, copy it to the position k and increment k.
  4. After the iteration, k will be the number of elements not equal to val.

Time Complexity: O(n)

Space Complexity: O(1)

Implementation

Java Solution

class Solution {
    public int removeElement(int[] nums, int val) {
        int k = 0; // pointer for the new array

        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[k] = nums[i];
                k++;
            }
        }

        return k;
    }
}

C++ Solution

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int k = 0; // pointer for the new array

        for (int i = 0; i < nums.size(); i++) {
            if (nums[i] != val) {
                nums[k] = nums[i];
                k++;
            }
        }

        return k;
    }
};

Explanation with Example

Let's walk through the solution using Example 2:

nums = [0,1,2,2,3,0,4,2], val = 2
  1. Initialize k = 0 and start iterating with i = 0.
  2. nums[0] = 0 != val, so we keep it: nums[0] = 0, k = 1
  3. nums[1] = 1 != val, so we keep it: nums[1] = 1, k = 2
  4. nums[2] = 2 == val, so we skip it: k remains 2
  5. nums[3] = 2 == val, so we skip it: k remains 2
  6. nums[4] = 3 != val, so we keep it: nums[2] = 3, k = 3
  7. nums[5] = 0 != val, so we keep it: nums[3] = 0, k = 4
  8. nums[6] = 4 != val, so we keep it: nums[4] = 4, k = 5
  9. nums[7] = 2 == val, so we skip it: k remains 5

After the iteration, k = 5, and the first 5 elements of nums are [0,1,3,0,4].

This approach is efficient because:

  1. It only requires a single pass through the array (O(n) time complexity).
  2. It doesn't use any extra space (O(1) space complexity).
  3. It modifies the array in-place, satisfying the problem requirement.

The order of elements may change, but the problem statement allows for this.