LeetCode Problem

Problem Description

Given an array nums and a value val, remove all instances of that value in-place and return the new length.

Examples

Input: [3,2,2,3], 3
Output: 2

Input: [0,1,2,2,3,0,4,2], 2
Output: 5

Constraints

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

Follow-up

Approach to Solve

Use two pointers to remove elements in-place.

Code Implementation

class Solution:
    def removeElement(self, nums: List[int], val: int) -> int:
        write_index = 0
        for read_index in range(len(nums)):
            if nums[read_index] != val:
                nums[write_index] = nums[read_index]
                write_index += 1
        return write_index

class Solution {
    public int removeElement(int[] nums, int val) {
        int writeIndex = 0;
        for (int readIndex = 0; readIndex < nums.length; readIndex++) {
            if (nums[readIndex] != val) {
                nums[writeIndex] = nums[readIndex];
                writeIndex++;
            }
        }
        return writeIndex;
    }

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int writeIndex = 0;
        for (int readIndex = 0; readIndex < nums.size(); readIndex++) {
            if (nums[readIndex] != val) {
                nums[writeIndex] = nums[readIndex];
                writeIndex++;
            }
        }
        return writeIndex;
    }

Explanation

This solution uses two pointers to remove elements in-place. Here's a detailed explanation of the algorithm:

Initialize the write index: Start with a write index of 0.
Iterate through the array: Use a read index to traverse the array.
Compare elements: For each element, compare it with the value to remove (val). If it's different, write it to the position indicated by the write index and increment the write index.
Return the new length: After the loop, the write index will be at the position where the last element that was not removed was written. This value represents the new length of the array after all instances of val have been removed.

This approach ensures that the elements are removed in-place and the relative order of the remaining elements is preserved. The time complexity is O(n), where n is the length of the array, because each element is processed exactly once.

Time Complexity: O(n), where n is the length of the array. Space Complexity: O(1), as we only use a constant amount of extra space for the write index.

Complexity

Time Complexity: O(n)
Space Complexity: O(1)

LeetSolved

Remove Element