Remove Element

The “Remove Element” problem challenges us to remove all occurrences of a given value from an array. While the task seems simple at first glance, finding the most efficient solution can be tough.

In this article, we will explore three different approaches to solve this problem, starting from a naive approach and gradually moving towards more optimized solutions.

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.

So let’s dive in and explore different approaches and their time and space complexities.

---

Approach 1: Naive Approach

1. Iterate through the array and check if each element is equal to the target value.

2. If an element is equal to the target, remove it from the array.

3. Repeat this process until all occurrences of the target value are removed.

4. Return the length of the array.

// ES6 Arrow Function
const removeElement = (nums, val) => {
    let i = 0; 
    while(i < nums.length) {
        if(nums[i] === val) nums.splice(i, 1);
        else i++;
    }

    return nums.length;
}

Time Complexity: O(N²)

In the worst case, we may have to remove all the elements of the array. Since removing an element takes O(N) time and we are doing that for N elements where N is the length of the array. It will take O(N²) time.

Space Complexity: O(1)

Since we are modifying the input array in-place, it doesn’t require any extra space. Hence, constant space complexity.

---

Approach 2: Two Pointers

1. Here we use two pointers, “slow” and “fast,” initially pointing to the start of the array.

2. Iterate through the array with the “fast” pointer.

3. When the “fast” pointer encounters an element that is not equal to the target, copy it to the position pointed by the “slow” pointer and increment both pointers.

Note: By doing so, we effectively remove the target value from the array. This approach avoids unnecessary removal operations, resulting in better performance than the naive approach.

4. Repeat this process until the “fast” pointer reaches the end of the array.

// ES6 Arrow Function
const removeElement = (nums, val) => {
    let slow = 0; 

    for(let fast = 0; fast < nums.length; fast++) {
        if(nums[fast] !== val) {
            nums[slow] = nums[fast];
            slow++;
        }
    }

    return slow;
}

Time Complexity: O(N)

Here we are iterating the input array once using the fast pointer. So it gives us the linear time complexity.

Space Complexity: O(1)

Since we are modifying the array in-place and not using any extra space the space complexity is constant.

---

Approach 3: Optimized Two Pointers

So the basic idea is to minimize the number of element swaps.

1. We use two pointers, “left” and “right,” initially pointing to the start and end of the array, respectively.

2. Move the “left” pointer to the right until it encounters an element equal to the target value.

3. Move the “right” pointer to the left until it encounters an element different from the target value.

4. If the “left” pointer is still to the left of the “right” pointer, swap the elements at these pointers and increment the “left” pointer and decrement the “right” pointer.

5. Repeat these steps until the “left” pointer is no longer to the left of the “right” pointer.

// ES6 Arrow Function
const removeElement = (nums, val) => {
    let left = 0; 
    let right = nums.length - 1;

    while(left <= right) {
        if(nums[left] === val) {
            [nums[left], nums[right]] = [nums[right], nums[left]];
            right--;
        } else {
            left++;
        }
    }

    return left;
}

Time Complexity: O(N)

In this approach, we reduce the number of swaps, but we still iterate through the array once. Therefore the time complexity is linear.

Space Complexity: O(1)

We are not using any extra space as we are modifying the input array in-place. So the space complexity is constant.

---

And there you have it guys! We’ve explored different approaches, optimized our solutions, and hopefully had some fun along the way. I hope this article has provided you with valuable insights and helped you better understand the different approaches to solving this problem. Happy coding!

Problem- Leetcode 27