LeetCode 27 Remove Element

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.

Difficulty
Easy

Analysis

Idea 1

Put elements that are not equal to target to the begining of the array. If those elements are not too many, this has a good time performance.

Idea 2

Use two indexers, one indexser i to iterate over the array, the other indexer j to record the index whose value equals to the target. Replace A[j] with a value A[i] that is not equal to target, j < i.

Improvements for idea 2

Index i iterate from the begining of the array, while j iterate from the end. Since we are shorting the length of array, the loop condition should be i <= newLen each time, the newLen is re-caculated.

Solutions

1. Cpp (idea 1)

class Solution {
public:
    int removeElement(vector<int> &A, int elem) {
        int n = A.size();
        int k = 0;
        for(int i = 0; i < n; i++)
            if(A[i] != elem) A[k++] = A[i];
        return k;
    }
};

1. Cpp (idea 2)

class Solution {
public:
    int removeElement(vector<int> &A, int val) {
        int n = A.size();
        int k = n-1;
        for(int i = 0; i <= k; i++)
            if(A[i] == val){
                while(k > i && A[k] == val) k--; // Find a value that is not equal to val
                if(k == i)return i;
                else A[i] = A[k--]; // put A[k], which is not equal to val, to position at i
            }
        return k + 1;
    }
};

1. Cpp (improvement of idea 2)

class Solution {
public:
    int removeElement(int A[], int n, int elem) {
        int k = n-1;
        for(int i = 0; i <= k;)
            if(A[i] == elem)
                A[i] = A[k--]; // put rear elements at current index i
            else i++;
        return k + 1;
    }
};

1. Go (improvement of idea 2)

func removeElement(nums []int, val int) int {
    if len(nums) < 1 {
        return 0
    }
    k := len(nums) - 1
    for i := 0; i <= k; {
        if nums[i] == val {
            nums[i] = nums[k]
            k--
        } else {
            i++
        }
    }
    return k + 1
}

Reference