8

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

3
  • What behavior do you want? Do you just want to ignore the parts of the array that do not exist, or what? Commented Feb 20, 2012 at 2:20
  • @peter i want to delete dups even if there are undefineds between Commented Feb 20, 2012 at 2:22
  • i think you should just pack the initial array into a temporary one (removing undefined values) and work with that for the duplicate checking.. Commented Feb 20, 2012 at 2:25

15 Answers 15

18

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.

Sign up to request clarification or add additional context in comments.

Comments

3

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]

1 Comment

i like this logic, flagging when first is better than checking if the array out length is 0
3

This is a one-liner:

uniquify( myArray.filter(function(x){return true}) )

If you don't already have uniquify written (the function you wrote to remove duplicates), you could also use this two-liner:

var newArray = [];
myArray.forEach(function(x) {
    if (newArray.length==0 || newArray.slice(-1)[0]!==x)
        newArray.push(x)
})

Elaboration:

var a=[];
a[0]=1; a[1]=undefined; a[2]=undefined;
a[10]=2; a[11]=2;

According to OP, array has "five elements" even though a.length==12. Even though a[4]===undefined, it is not an element of the array by his definition, and should not be included.

a.filter(function(x){return true}) will turn the above array into [1, undefined, undefined, 2, 2].


edit: This was originally written with .reduce() rather than .forEach(), but the .forEach() version is much less likely to introduce garbage-collector and pass-by-value issues on inefficient implements of javascript.

For those concerned about compatibility with the 6-year-old MIE8 browser, which does not support the last two editions of the ECMAScript standard (and isn't even fully compliant with the one before that), you can include the code at https://developer.mozilla.org/en/JavaScript/Reference/Global_Objects/Array/forEach However if one is that concerned about browser compatibility, one ought to program via a cross-compiler like GWT. If you use jQuery, you can also rewrite the above with only a few extra characters, like $.forEach(array, ...).

6 Comments

Note that this requires a modern browser that supports Array.reduce. For example, this will not work on <=IE8.
Thank you for your concern. However it's been over half a decade since IE8 was released. The operating system it was released on has been officially end-of-life by Microsoft for years. Even on Windows 7, according to computerworld.com/s/article/9215845/… Microsoft has begun offering PUSHED popup downloads to computers who happen to still be using IE8 (and that was a year ago). This has been in the ECMAScript 5 standard since 2009. Programming without Array.map()/.filter()/.forEach() is a pain without compare and reminiscent of C.
I am not talking about those undefined, I am talking about the undefineds that won't be alerted here for(var i=0;i<array.length;i++){if(i in array){alert(array[i]);}}
@ninjagecko 2009 isn't "over half a decade ago", and IE<=8 still has more than twice the market share of IE9, so I think it's still a valid concern.
(The first non-beta) IE8 was released in 2009, and as of December 2011 still had a 22% market share, but if you're happy to disregard one in five potential users go right ahead. Note that lots of people are prevented from using IE9 due to worksite IT policy restrictions (e.g., at my current workplace we are still on XP and IE_7_).
|
2

Perhaps something like this:

var out = [],
    prev;

for(var i = 0; i < arr.length; i++) {
   if (!(i in arr))
      continue;

   if (arr[i] !== prev || out.length === 0) {
      out.push(arr[i]);
      prev = arr[i];
   }
}

The out.length check is to allow for the first defined array element having a value of undefined when prev also starts out initially as undefined.

Note that unlike your original algorithm, if arr is empty this will not push an undefined value into your out array.

Or if you have a new enough browser, you could use the Array.forEach() method, which iterates only over array elements that have been assigned a value.

5 Comments

Perfect. I will just change the equality symbols to arr[i] !== prev and out.length == 0. (I think this is what you mean in first place)
Thanks. Yes, I should've said arr[i] !== prev - good catch - I've updated my answer to reflect this. But I did mean out.length === 0 (array length will always be numeric).
"array length will always be numeric", so why the ===?
Why not ===? I use == only went I want to be able to compare operands of (potentially) different types that might be coerced to the same type and value.
I only use === and !== when I think coercing might produce unexpected stuff, if I know exactly what I am dealing with, and that == or != won't ever get me into problems, I will use them and save 1 char
1

An explicit way would be to pack the array (remove the undefined) values and use your existing algorithm for the duplicates on that..

function pack(_array){
    var temp = [],
        undefined;
    for (i=0, len = _array.length; i< len; i++){
        if (_array[i] !== undefined){
            temp.push(_array[i]);
        }   
    }
    return temp;
}

2 Comments

The "pack" idea was my first impulse too, and bonus points for making sure that undefined really is undefined, but note that your implementation doesn't meet the OP's requirement to distinguish between array elements that have been assigned the value undefined (which are to be kept) and indexes that have not ever had a value assigned (which are to be skipped over).
@nnnnnn, hmm.. Valid point, although i am not sure if that was indeed the OP concern.. i read it as just an explanation that values are really undefined.. not that he wanted a different handling for them..
1

I think this is what you want. It's a pretty simple algorithm.

var out = [], previous;
for(var i = 0; i < arr.length; i++) {
  var current = arr[i];
  if(!(i in arr)) continue;
  if(current !== previous) out.push(current);
  previous = arr[i];
}

This will run in O(N) time.

5 Comments

This doesn't meet the OP's requirement to distinguish between array elements that have been assigned the value undefined (which are to be kept) and indexes that have not ever had a value assigned.
@nnnnnn I'm not sure I understand, I asked him what behavior he wanted, and he just said to delete dupes even if there are undefineds in between. Does he not want dupes to be deleted for arrays that have values that are assigned to undefined between duplicate values?
Consider: var arr=[]; arr[5]=1; arr[9]=undefined; arr[11]=undefined; arr[13]=3 - after that code arr.length is 14, but index positions 0-4, 6-8, 10 & 12 have never been assigned a value and it is those that the OP wants to skip over. Indexes 9 & 11 have been explicitly assigned undefined and should not be skipped. OP mentioned this under the "Question" heading halfway through the post, but didn't explain it very well. And then the comment that was meant to clarify actually made it less clear (so maybe I've misinterpreted).
@PeterOlson I meant undefineds that don't hold the undefined value. In other words, they won't appear in here for(i=0;i<array.length;i++){if(i in array){alert(array[i]);}}
yep, that is what I was looking for. I am sorry that my not-so-clear instructions lead you to answer it after 'nnnnnn'. I take full responsibility for what happened here.
1

A very simple function, the input array must be sorted:

function removeDupes(arr) {
  var i = arr.length - 1;
  var o;
  var undefined = void 0;

  while (i > 0) {
    o = arr[i];

    // Remove elided or missing members, but not those with a 
    // value of undefined 
    if (o == arr[--i] || !(i in arr)) {
      arr.splice(i, 1);
    }
  }
  return arr;
}

It can probably be more concise, but might become obfuscated. Incidentally, the input array is modified so it doesn't need to return anything but it's probably more convenient if it does.

Here's a forward looping version:

function removeDupes2(arr) {
  var noDupes = [],
      o;

  for (var i=0, j=0, iLen=arr.length; i<iLen; i++) {
    o = arr[i];
    if (o != noDupes[j] && i in arr) {
       noDupes.push(o);
       j = noDupes.length - 1;
    }
  }
  return noDupes;
}

PS

Should work on any browser that supports javascript, without any additional libraries or patches.

2 Comments

it removes both the items that hold the undefined value, and the fake undefined ones. (I only want to remove the fake ones)
Very simple edit to change that (done), though it's a strange requirement
1

This solution removes duplicates elements in-place. not recommended for functional programming

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

const removeDuplicates = (nums) => {
  nums.forEach((element, idx) => {
    nums.splice(idx, nums.lastIndexOf(element) - idx)
  })
}

removeDuplicates(arr)

console.log(arr);

Comments

0
//sort the array
B.sort(function(a,b){ return a  - b});
//removing duplicate characters
    for(var i=0;i < B.length; i ++){
        if(B[i]==B[i + 1])
            B.splice(i,1)
    }

if element in next index and current position is same remove the element at current position

splice(targetPosition,noOfElementsToBeRemoved)

Comments

0

I believe what you are trying to achieve is not quite possible, but I could be wrong.

It's like one of those classic CS problems like the one where a barber in a village only shaves the one who don't shave themselves. If you set the value of an array's index item as undefined, it's not really undefined. Isn't that the case? A value can only be undefined when it hasn't been initialized.

What you should be checking for is whether a value is null or undefined. If null or duplicate skip the value, else retain it.

If null values and duplicates are what you are trying to skip then below function will do the trick.

function  removeDuplicateAndNull(array){

    if(array.length==0)
        return [];

    var processed = [], previous=array[0];
    processed.push(array[0]);

    for(var i = 1; i < array.length; i++) {

        var value = array[i];

        if( typeof value !== 'undefined' && value ==null) 
            continue;

        if(value !== previous || typeof value === 'undefined')
            processed.push(value);

        previous = array[i];
    }
    return processed;
}

Test cases:

  1. array=[,5,5,6,null,7,7] output =[ ,5,6,7]

  2. array=[ 5,5,,6,null,,7,7] output=[5,,6,,7]

  3. array=[7,7,,] output=[7,]

But even with this function there's a caveat. IF you check third test, the output is [7,] instead of [7,,] ! If you check the length of the input and output arrays, array.length =3 and output.length=2. The caveat is not with the function but with JavaScript itself.

1 Comment

the accepted ans works, it filters the undefined but respecting the manually-set undefined. Use his code with -> var arr=[];arr[3]=1;arr[5]=undefined;arr[6]=undefined;arr[8]=true;arr[10]=true; and the output should be 1,,true
0

This code is written in javascript. Its very simple.

Code:

function remove_duplicates(arr) {
        newArr = [];
        if (arr.length - 1 >= 0) {
            for (i = 0; i < arr.length - 1; i++) {
                // if current element is not equal to next
                // element then store that current element
                if (arr[i] !== arr[i + 1]) {
                    newArr.push(arr[i]);
                }
            }
            newArr.push(arr[arr.length - 1]);
        }
        return newArr
    }
    arr=[0,1,1,2,2,3,4,5,5,6,7,7,8,9,9,9];
    console.log(remove_duplicates(arr));

Comments

0

Here is the simple JavaScript solution without using any extra space.

function removeDuplicates(A) {
   let i = 0;
   let j = i + 1;
   while (i < A.length && j < A.length) {
      if (A[i] === A[j]) {
         A.splice(i, 1);
         j=i+1;
       } else {
         i++;
         j++;
        }
     }
    return A;
   }
console.log('result', removeDuplicates([0,1,1,2,2,2,2,3,4,5,6,6,7]))

Comments

0

You can try the simple way

function hello(a: [], b: []) {
     return [...a, ...b];
}
let arr = removeDuplicates(hello([1, 3, 7], [1, 5, 10]));
arr = removeDuplicates(arr);
function removeDuplicates(array) {
  return array.filter((a, b) => array.indexOf(a) === b);
}
let mainarr = arr.sort((a, b) => parseInt(a) - parseInt(b));
console.log(mainarr); //1,3,5,7,10

One liner code

[1,3,7,1,5,10].filter((a, b) => [1,3,7,1,5,10].indexOf(a) === b).sort((a, b) => parseInt(a) - parseInt(b))

Comments

0

Here is simple solution to remove duplicates from sorted array.

Time Complexity O(n)

function removeDuplicate(arr) {
        let i=0;
        let newArr= [];
        while(i < arr.length) {
            if(arr[i] < arr[i+1]) {
                newArr.push(arr[i])
            } else if (i === (arr.length-1)) {
                newArr.push(arr[i])
            }
            i++;
        }
        return newArr;
    }
    var arr = [1,2,3,4,4,5,5,5,6,7,7]
    console.log(removeDuplicate(arr))

Comments

0

Let's suppose that you have a sorted array and you can't use additional array to find and delete duplicates:

In Python

def findDup(arr, index=1, _index=0):

    if index >= len(arr):
        return

    if arr[index] != arr[_index]:

        findDup(arr, index+1, _index+1)

    if arr[index] == arr[_index]:
        arr = deletedup(arr, index)
        findDup(arr, index, _index) #Has to remain same here, because length has changed now



def deletedup(arr, del_index):
    del arr[del_index]
    return arr

arr = [1, 2, 3, 4, 4, 4, 5, 6, 7, 7, 7, 7, 7]

findDup(arr)
print arr

Comments

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.