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 in place with constant memory.

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

Example:
Given input array nums = [3,2,2,3], val = 3

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

Solution

Easy brute force: O(n) time and O(1) space

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

Optimal solution using Swap: O(n) time and O(1) space

public class Solution {
    public int removeElement(int[] nums, int val) {
        if (nums == null) return 0;
        int i = 0, n = nums.length;
        while (i < n) {
            if (nums[i] == val) {
                nums[i] = nums[n - 1]; //cannot update i to i++ here, cause the nums[n-1] might == val too 
                n--;
            }
            else i++;
        }
        return i;
    }
}

Analysis

This is a very easy array problem
All we need to do is to go through the array and update the value in place
The first solution is good but it always copies the value of array if nums[i] != val
The second solution avoid this unnecessary copy by using swap
We swap the current num with num[n - 1] if we have to remove
Then we update n-- and exit the while loop as long as i < n not satisfied