LeetCode: 27. Remove Element

The Problem

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.

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

Constraints:

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

The Solution

Solution A

We opted for a simple approach using a for loop

int removeElement(vector<int>& nums, int val) {

	int i = 0, j = nums.size() - 1, count = 0;

	for(; i <= j; ++i) {

		if(nums[i] == val){
			for(; j > i; --j){
				if(nums[j] != val) {
					swap(nums[i], nums[j]);
					break;
				}
			}
		}

		count += nums[i] != val;
	}

	return count;
}

Here's how it works:

1. It initializes three variables: i which starts at index 0, j which starts at the last index of the vector nums, and count which counts the number of elements in the vector after removing val.
2. It enters a loop that iterates as long as i is less than or equal to j.
3. Inside the loop, it checks if the element at index i is equal to the value val. If it is, it enters another loop starting from the end of the vector (index j) and moving towards i. It looks for the first element from the end that is not equal to val, then swaps it with the element at index i and breaks out of the loop.
4. After swapping, or if no swapping occurs, it increments i.
5. Regardless of whether swapping occurs or not, it increments count if the element at index i is not equal to val. This is because we are counting the elements that are not equal to val as they are the ones that will remain in the vector after removal.
6. After the loop completes, it returns the value of count, which represents the number of elements in the vector nums after removing all occurrences of val.

Solution B

We opted for a more convenient approach using a for loop

int removeElement(vector<int>& nums, int val) {

	int index = 0;

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

Here's how it works:

1. It initializes an integer variable index to 0. This variable will keep track of the index where non-val elements should be placed in the modified nums.
2. It iterates through each element of the vector nums using a for loop with index i.
3. Inside the loop, it checks if the current element nums[i] is not equal to the value val. If it's not equal, it means this element should be kept in the modified vector.
4. If the current element is not equal to val, it assigns this element to the position index in the vector nums and then increments index. This effectively moves non-val elements towards the beginning of the vector.
5. After the loop completes, it returns the value of index. This value represents the number of elements in the modified vector nums after removing all occurrences of val, and it also serves as the new size of the vector.