Leetcode: Remove Element

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

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

Understand the problem:
The problem gives an array and a value, remove all instances of that value in-place and return the new length. 

Several special requirements for this question: The order of elements can be changed. It doesn't matter what you leave beyond the new length. 

Naive Solution:
Since the problem only asks about the new length of the array. The most straight-forward solution is to traverse the array. For the element equals to the input value, we deduct the length. In this way, we actually did not remove the desired elements in the array.

Code (Java):

public class Solution {
    public int removeElement(int[] A, int elem) {
        if (A == null || A.length == 0) return 0;
        
        int len = A.length;
        
        for (int i = 0; i < A.length; i++) {
            if (A[i] == elem) len--;
        }
        return len;
    }
}

However, it failed on the OJ test. 
Input:[4,5], 4
Output:[4]
Expected:[5]

So it looks like that OJ does check the final array. We must come out a new solution with changing to the output array.

Wrong Solution:
Iterate through the array from left, if found a target value, move all the elements behind one step left. The code is as below:

Code (Java):

public class Solution {
    public int removeElement(int[] A, int elem) {
        if (A == null || A.length == 0) return 0;
        
        int len = A.length;
        
        for (int i = 0; i < A.length; i++) {
            if (A[i] == elem) {
                for (int j = i + 1; j < A.length; j++) {
                    A[j - 1] = A[j];
                }
                len--;
            }
        }
        return len;
    }
}

Why it is wrong. If the target elements are at head of tail of the array, it will get the wrong result. 

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

Correct Solution:
The correct solution is traverse the array backward. 

public class Solution {
    public int removeElement(int[] A, int elem) {
        if (A == null || A.length == 0) return 0;
        
        int len = A.length;
        
        for (int i = A.length - 1; i >= 0; i--) {
            if (A[i] == elem) {
                for (int j = i + 1; j < A.length; j++) {
                    A[j - 1] = A[j];
                }
                len--;
            }
        }
        return len;
    }
}

Discussion:
The time complexity of the solution is O(n^2), since we need to move the elements. The space complexity is O(1). 
A Better Solution:
Does there exist an O(n) time solution? The answer is yes. We can iterate the array, for the element not equal to the target value, we increase a counter and overwrite the element of i to counter. For the equal element, we don't increase the counter. As a result, the removed elements will be overwritten by its following elements. 

Code (Java):

public class Solution {
    public int removeElement(int[] A, int elem) {
        if (A == null || A.length == 0) return 0;
        
        int counter = 0;
        for (int i = 0; i < A.length; i++) {
            if (A[i] != elem) {
                A[counter++] = A[i];
            }
        }
        return counter;
    }
}

Summary:
Take away message from this problem: This is a classical removing elements in an array problem. Using two pointers is a common idea where one points to the overwritten element, one points to the reading element.