Coding Exercise – Remove Element – C++ – Online Judge

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

The order of elements can be changed and it doesn’t matter what you leave beyond the new length.

Original Problem Page: http://oj.leetcode.com/problems/remove-element/

There are two important hints: (1) the order of elements can be changed, meaning that we can swap elements for our conveniences. (2) it doesn’t matter what we leave beyond the new length, meaning that we don’t need to care the values (don’t need to preserve their original values even we don’t need it)

Could someone think of a shorter solution than this?

1
2
3
4
5
6
7
8
9
10
11

class Solution {
public:
    int removeElement(int A[], int n, int elem) {
        for (int i = 0; i < n; i ++) {
            while ((A[i] == elem) && (i < n) && (n > 0)) {
                A[i] = A[n-- - 1]; // swap current with the end and n--
            }
        }
        return n;
    }
};

class Solution {
public:
    int removeElement(int A[], int n, int elem) {
        for (int i = 0; i < n; i ++) {
            while ((A[i] == elem) && (i < n) && (n > 0)) {
                A[i] = A[n-- - 1]; // swap current with the end and n--
            }
        }
        return n;
    }
};

Check each position, and swap it (not actually) with the current end, so the element at the end jumps to the current position and overwrites its value (it is lost, but we don’t care). Remember to decrement the length with n–.

Again, this is done in place (no additional space is required). We have a while loop to check if the value at the end is still to be removed, so we can continue removing them until it is not. It looks like But in fact, it is practically complexity, do you know why? 🙂

—EOF–