deleting duplicates on sorted array

Question

Just in case you missed, the question is about deleting duplicates on a sorted array. Which can be applied very fast algorithms (compared to unsorted arrays) to remove duplicates.

• You can skip this if you already know how deleting duplicates on SORTED arrays work

Example:

var out=[];
for(var i=0,len=arr.length-1;i<len;i++){
    if(arr[i]!==arr[i+1]){
        out.push(arr[i]);
    }
}
out.push(arr[i]);

See?, it is very fast. I will try to explain what just happened.

The sorted arrays *could look like this:

arr=[0,1,1,2,2,3,4,5,5,6,7,7,8,9,9,9];

*the sorting could be ASC or DESC, or by other weird methods, but the important thing is that every duplicated item is next each other.

We stopped at array.length-1 because we don't have anything to check with

Then we added the last element regardless of anything because:

case A:

... ,9,9,9];//we have dup(s) on the left of the last element

case B:

... ,7,9,10];//we don't have dup(s) on the left of the last element

If you really understand what is happening, you will know that we haven't added any 9 on the case A. So because of that, we want to add the last element no matter if we are on case A or B.

---

Question:

That explained, I want to do the same, but ignoring the undefined value on cases like:

var arr=[];arr[99]=1;//0 through 98 are undefined, but do NOT hold the undefined value

I want to remove those. And on the case I have some real undefined values, these should not be removed.

My poor attempt is this one:

var out=[];
for (var i=0,len=arr.length; i < len - 1;) {
  var x = false;
  var y = false;

  for (var j = i, jo; j < len - 1; j++) {
    if (j in arr) {
      x = true;
      jo = arr[j];
      i = j + 1;
      break;
    }
  }
  if (x == false) {
    break;
  }

  for (var u = i, yo; u < len - 1; u++) {
    if (u in arr) {
      y = true;
      yo = arr[u];
      i = u + 1;
      break;
    }
  }
  if (y == false) {
    out.push(jo);
    break;
  }

  if (jo !== yo) {
    out.push(jo);
  }
}
out.push(arr[len - 1]);

I am really lost, any help is appreciated

Answer 1

A modern one-liner using .filter()

arr.filter((e, i, a) => e !== a[i - 1]);

I'm very surprised by the complexity of other answers here, even those that use .filter()

Even using old-school ES5 syntax with no arrow functions:

arr.filter(function (e, i, a) { return e !== a[i - 1] });

Example:

let a = [0, 1, 1, 2, 2, 3, 4, 5, 5, 6, 7, 7, 8, 9, 9, 9];

let b = arr.filter((e, i, a) => e !== a[i - 1]);

console.log(b); // [ 0, 1, 2, 3, 4, 5, 6, 7, 8, 9 ]

If you need to mutate the array in place then just use:

arr = arr.filter((e, i, a) => e !== a[i - 1]);

Personally I would recommend against using such complex solutions as the ones in other answers here.

Answer 2

For a start, I'm not entirely certain your original code is kosher. It appears to me that it may not work well when the original list is empty, since you try to push the last element no matter what. It may be better written as:

var out = [];
var len = arr.length - 1;
if (len >= 0) {
    for (var i = 0;i < len; i++) {
        if (arr[i] !== arr[i+1]) {
            out.push (arr[i]);
        }
    }
    out.push (arr[len]);
}

As to your actual question, I'll answer this as an algorithm since I don't know a lot of JavaScript, but it seems to me you can just remember the last transferred number, something like:

# Set up output array.

out = []

# Set up flag indicating first entry, and value of last added entry.

first = true
last = 0

for i = 0 to arr.length-1:
    # Totally ignore undefined entries (however you define that).

    if arr[i] is defined:
        if first:
            # For first defined entry in list, add and store it, flag non-first.

            out.push (arr[i])
            last = arr[i]
            first = false
        else:
            # Otherwise only store if different to last (and save as well).

            if arr[i] != last:
                out.push (arr[i])
                last = arr[i]