Arrays - Remove Element

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.

Input: numRows = 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).

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

Solution using in-place removal of elements using two pointers

In this approach, we are going to use in-place removal of elements using two pointers.

We will create a function inPlaceRemovalUsingTwoPointers that takes input arguments nums and val.
We are then going to create a variable count that we are going use to count how many elements are left after removal of elements whose value is equal to val, we are also going to use this as one of the pointer in this two pointers approach.
Then, for each element at index i check if the value is equal to val, if it is not equal then copy element at index i to index count and increment count.

The reason why we do this is because, consider an example with input array as [1, 1, 2, 3] and val=1, so we have to remove 1 from array and return how many elements left after it is removed.

Initially both count and i are going to be 0.
When we are at 1^st element 1, we will not do anything since it is the val to be removed and we move i to 1.
When we are at 2^nd element 1, we will not do anything at this element either and move i to 2.
When we are at 3^rd element 2, since this is not equal to the element that we want to remove, we will copy this to count index and increment counter, so it becomes 1. Now the resultant array looks like this [2, 1, 2, 3]
When we are at 4^th element 3, since this is not equal to the element that we want to remove, we will copy this to count index and increment counter, so it becomes 2. Now the resultant array looks like this [2, 3, 2, 3]
If you observer, count holds, how many elements were left which are not equal to val after it is removed and all the values that are not equal to are moved to the beginning of array.
In short, we have moved elements to the left that are not equal to val and left other elements as they are not needed to be looked at, as per problem statement. (Incase if the val need to be moved to right side, then we can swap elements instead just copying)

Finally, just return count, which holds how many elements are left after removal of val.

public class RemoveElements { /* in-place removal of element using two pointers */ static int inPlaceRemovalUsingTwoPointers(int[] nums, int val) { int count = 0; for(int i=0; i<nums.length; i++) { if(nums[i] != val) { nums[count] = nums[i]; count++; } } return count; } }

Complexity Analysis:

Time complexity: Above code runs in O(n) time where n is the input array nums length. This is because, we are looping through nums array only once.
Space complexity: O(1).

Above implementations source code can be found at GitHub link for Java code

Custom Judge:

Constraints:

Contents

Complexity Analysis: