Leetcode 27- Remove Element from Array

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];
}

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

Problem Link : Remove Element – LeetCode

Solution:

Approach 1: Brute Force Solution to Remove Element from Array

A simple brute-force solution involves iterating through the array and copying all elements that are not equal to val into a new array. Once the iteration is complete, the length of the new array will be the number of elements that do not equal val.

class Solution {
    public int removeElement(int[] nums, int val) {
        int[] temp = new int[nums.length];
        int j = 0; // pointer for temp array

        // Traverse the array and copy elements that are not equal to val
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                temp[j] = nums[i];
                j++;
            }
        }

        // Copy back the elements from temp array to nums array
        for (int i = 0; i < j; i++) {
            nums[i] = temp[i];
        }

        return j; // j is the new length
    }
}

Explanation:

• Create a temporary array temp to store elements that are not equal to val.
• Traverse the nums array, and if the current element is not equal to val, copy it to temp.
• Once the traversal is complete, copy elements from temp back into nums and return the length of temp (denoted by j).

Time and Space Complexities:

• Time Complexity: O(n): We traverse the array twice, once to build the temp array and again to copy the elements back.
• Space Complexity:O(n): We use an extra array temp of size n to store the valid elements.

Approach 2: In-Place Solution Using Two Pointers to Remove Element from Array:

To improve on the brute-force approach, we can eliminate the need for extra space by using the two-pointer technique. We’ll have one pointer that iterates through the array (i) and another pointer (j) that keeps track of the position where the next non-val element should be placed.

Java Code:

  class Solution {
    public int removeElement(int[] nums, int val) {
        int j = 0; // pointer for the new position of non-val elements

        // Traverse the array
        for (int i = 0; i < nums.length; i++) {
            if (nums[i] != val) {
                nums[j] = nums[i]; // Move the non-val element to the current position of j
                j++; // Increment the position for the next non-val element
            }
        }

        return j; // j is the new length of the array
    }
}

Explanation:

• We use a single pass to iterate through the array.
• If the current element nums[i] is not equal to val, we copy it to the position j and then increment j.
• After the loop, j holds the number of elements that are not equal to val and the array is modified in-place.

Time and Space Complexities:

• Time complexity:O(n) as we traverse the array only once.
• Space complexity:O(1) since no extra space is used, as the modification is done in-place.

Approach 3: Optimal Two Pointers with Minimized Operations to Remove Element from Array

In the second approach, we are still copying elements even if they are already in their correct positions. To optimize this further, we can use a two-pointer technique that works from both ends of the array. This helps reduce the number of unnecessary assignments when the element to be removed is already at the end of the array.

Java Code:

class Solution {
    public int removeElement(int[] nums, int val) {
        int i = 0; // Start pointer
        int n = nums.length; // Length of the array

        while (i < n) {
            if (nums[i] == val) {
                nums[i] = nums[n - 1]; // Replace the current element with the last element
                n--; // Decrease the array size (ignore the last element)
            } else {
                i++; // Move to the next element
            }
        }

        return n; // n is the new length of the array
    }
}

Explanation:

• We start with two pointers: i starting from the beginning and n as the length of the array.
• If nums[i] equals val, replace it with the last element nums[n - 1] and decrease n. This effectively removes the element at index i.
• If nums[i] is not equal to val, increment i to check the next element.
• The loop continues until i is equal to n.

This method reduces unnecessary overwrites because when val is found, the replacement happens with the last element, which will not be part of the final array.

Time and Space Complexities:

• Time Complexity:O(n): We only traverse the array once, potentially skipping elements that are already at the end of the array.
• Space Complexity:O(1): No extra space is required.

Conclusion:

For LeetCode Problem 27 – Remove Element, the most optimal solution is the two-pointer technique that works from both ends of the array. It minimizes unnecessary writes, ensuring efficient in-place removal of elements. Understanding how to apply such techniques can significantly improve the performance of your solutions in coding challenges.