Remove Element

• LeetCode: Remove Element

• Problem:

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

Do not allocate extra space for another array, you must do this by modifying the input array in-place with O(1) extra memory.

The order of elements can be changed. It doesn't matter what you leave beyond the new length.

• Examples:

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

Your function should return length = 2, with the first two elements of nums being 2.

• Analysis:

Use two pointers, left and right.

The left pointer is to scan for the target removed element.

The right pointer is to scan for the not target element.

And then, swap

• Code - Java:

class Solution {
    public int removeElement(int[] nums, int val) {
        int len = nums.length;
        int left = 0;
        int right = len - 1;
        while (left <= right) {
            if (left <= right && nums[left] != val) {
                left++;
                continue;
            }
            if (right >= left && nums[right] == val) {
                right--;
                continue;
            }
            if (left > right) {
                break;
            }
            swap(nums, left, right);
        }
        return left;
    }
    private void swap(int[] nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
}

• Code - C++:

class Solution {
public:
    int removeElement(vector<int>& nums, int val) {
        int len = nums.size();
        int left = 0;
        int right = len - 1;
        while (left <= right) {
            if (left <= right && nums[left] != val) {
                left++;
                continue;
            }
            if (right >= left && nums[right] == val) {
                right--;
                continue;
            }
            if (left > right) {
                break;
            }
            swap(nums, left, right);
        }
        return left;
    }
    void swap(vector<int>& nums, int left, int right) {
        int temp = nums[left];
        nums[left] = nums[right];
        nums[right] = temp;
    }
};

• Code - Python:

class Solution(object):
    def removeElement(self, nums, val):
        """
        :type nums: List[int]
        :type val: int
        :rtype: int
        """
        numsLen, left, right = len(nums), 0, len(nums) - 1
        while left <= right:
            if left <= right and nums[left] != val:
                left += 1
                continue
            if right >= 0 and nums[right] == val:
                right -= 1
                continue
            if left > right:
                break
            self.swap(nums, left, right)
        return left
    def swap(self, nums, left, right):
        nums[left], nums[right] = nums[right], nums[left]

• Code - C:

void swap(int* nums, int left, int right) {
    int temp = nums[left];
    nums[left] = nums[right];
    nums[right] = temp;
}

int removeElement(int* nums, int numsSize, int val) {
    int len = numsSize;
    int left = 0;
    int right = len - 1;
    while (left <= right) {
        if (left < len && nums[left] != val) {
            left++;
            continue;
        }
        if (right >= 0 && nums[right] == val) {
            right--;
            continue;
        }
        if (left > right) {
            break;
        }
        swap(nums, left, right);
    }
    return left;
}

• Time Complexity: O(N), N is the length of input array

• Space Complexity: O(1)