Remove Element

27.Remove Element

Array

Two Pointers

Problem Statement:

Given an integer array nums and a value val, remove all instances of val in nums in-place and return the new length. The order of elements may be changed.

Example:

Input:

nums = [3,2,2,3], val = 3

→

Output:

2, nums = [2,2,_,_]

Algorithm:

1. Use two pointers from start and end
2. Replace target values with end elements
3. Decrement end pointer when replacing
4. Return new length of array

Complexity:

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

Java Solution:

public int removeElement(int[] nums, int val) {
    int i = 0;
    int j = nums.length - 1;
    
    while (i <= j) {
        if (nums[i] == val) {
            nums[i] = nums[j];  // Replace with last element
            j--;
        } else i++;
    }
    
    return j + 1;
}

// Not needed since end elements don't matter
public void swap(int[] nums, int i, int j) {
    int a = nums[i];
    nums[i] = nums[j];
    nums[j] = a;
}

Python Solution:

def removeElement(self, nums: List[int], val: int) -> int:
    i = 0
    j = len(nums) - 1
    
    while i <= j:
        if nums[i] == val:
            nums[i] = nums[j]  # Replace with last element
            j -= 1
        else:
            i += 1
    
    return j + 1

C++ Solution:

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int i = 0;
        int j = nums.size() - 1;
        
        while (i <= j) {
            if (nums[i] == val) {
                nums[i] = nums[j];  // Replace with last element
                j--;
            } else {
                i++;
            }
        }
        
        return j + 1;
    }
};