LeetCode #27 - Remove Element

Hello, coding enthusiasts! 🖐️ Today, we’re tackling the “Remove Element” problem from LeetCode.

We’re given an array nums and a value val, and we need to remove all instances of that value in-place and return the new length.

Let’s dive into it!

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.

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.

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

Analysis

This problem is a classic example of the two-pointer technique in arrays. The idea is to maintain two pointers – one for the current element and the other for the next non-duplicate element.

We iterate through the array, comparing the current element with the given value. If they are the same, we move on to the next element.

If they are different, we copy the next element to the current position and move both pointers forward.

Approach

Initialize two pointers: We start by initializing two pointers i and j at the beginning of the array. i points to the position where the next non-duplicate element should be placed, and j is used to scan through the array.
Iterate through the array: We iterate through the array using the j pointer.
Compare current element with the given value: During each iteration, we compare the current element nums[j] with the given value val.
Copy next element to current position: If nums[j] is not equal to val, it means nums[j] is the next non-duplicate element. So, we copy nums[j] to nums[i] and increment i.
Repeat the process: We repeat the process until j has scanned the entire array.
Return length: The length of the array without the given value will be i, as i is the position of the last non-duplicate element in the array.

Time Complexity

The time complexity of this algorithm is O(n), where n is the length of the array. This is because we are scanning through the array only once.

Space Complexity

The space complexity is O(1), as we are not using any additional space that scales with the input size. All operations are done in-place.

Code

Python

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        i = 0
        for j in range(len(nums)):
            # If the current element is not the value to be removed
            if nums[j] != val:
                # Copy the current element to the i-th position
                nums[i] = nums[j]
                # Increment the counter
                i += 1
        # Return the length of the array without the given value
        return i

JavaScript

var removeElement = function(nums, val) {
    let i = 0;
    for (let j = 0; j < nums.length; j++) {
        if (nums[j] != val) {
            nums[i] = nums[j];
            i++;
        }
    }
    return i;
};

Conclusion

And there you have it! We’ve successfully solved the “Remove Element” problem using the two-pointer technique.

The key takeaway here is the concept of maintaining two pointers – one for the current element and the other for the next non-duplicate element. This approach allows us to efficiently scan through the array and remove duplicates.

Happy coding!

Learn More:

LeetCode #27 – Remove Element