I need to add an element to an array only if it is not already there in Javascript. Basically I'm treating the array as a set.

I need the data to be stored in an array, otherwise I'd just use an object which can be used as a set.

I wrote the following array prototype and wanted to hear if anyone knew of a better way. This is an O(n) insert. I was hoping to do O(ln(n)) insert, however, I didn't see an easy way to insert an element into a sorted array. For my applications, the array lengths will be very small, but I'd still prefer something that obeyed accepted rules for good algorithm efficiency:

Array.prototype.push_if_not_duplicate = function(new_element){
    for( var i=0; i<this.length; i++ ){
        // Don't add if element is already found
        if( this[i] == new_element ){
            return this.length;
        }
    }
    // add new element
    return this.push(new_element);
}

I need to add an element to an array only if it is not already there in Javascript. Basically I'm treating the array as a set.

I need the data to be stored in an array, otherwise I'd just use an object which can be used as a set.

I wrote the following array prototype and wanted to hear if anyone knew of a better way. This is an O(n) insert. I was hoping to do O(ln(n)) insert, however, I didn't see an easy way to insert an element into a sorted array. For my applications, the array lengths will be very small, but I'd still prefer something that obeyed accepted rules for good algorithm efficiency:

Array.prototype.push_if_not_duplicate = function(new_element){
    for( var i=0; i<this.length; i++ ){
        // Don't add if element is already found
        if( this[i] == new_element ){
            return this.length;
        }
    }
    // add new element
    return this.push(new_element);
}

• javascript
• arrays
• sorting
• set

Share Improve this question Follow edited May 15, 2015 at 5:05 Kara 6,2261616 gold badges5353 silver badges5858 bronze badges asked Oct 3, 2011 at 18:08 Chris DutrowChris Dutrow 50.5k6767 gold badges196196 silver badges262262 bronze badges 2

• 2 You say that it is a sorted array, but I don't see how your algorithm enforces any order. Am I missing something? – RustyTheBoyRobot Commented Oct 3, 2011 at 18:33
• Hey Rusty, sort is not enforced for this array because the algorithm checks all elements in the array before insertion. To insert a unique element at O(ln(n)), the array would have to already be sorted. – Chris Dutrow Commented Oct 3, 2011 at 18:48

Add a ment  | 

4 Answers 4

Sorted by: Reset to default 4

If I understand correctly, you already have a sorted array (if you do not have a sorted array then you can use Array.sort method to sort your data) and now you want to add an element to it if it is not already present in the array. I extracted the binary insert (which uses binary search) method in the google closure library. The relevant code itself would look something like this and it is O(log n) operation because binary search is O(log n).

function binaryInsert(array, value) {
  var index = binarySearch(array, value);
  if (index < 0) {
    array.splice(-(index + 1), 0, value);
    return true;
  }
  return false;
};

function binarySearch(arr, value) {
  var left = 0;  // inclusive
  var right = arr.length;  // exclusive
  var found;
  while (left < right) {
    var middle = (left + right) >> 1;

    var pareResult = value > arr[middle] ? 1 : value < arr[middle] ? -1 : 0;
    if (pareResult > 0) {
      left = middle + 1;
    } else {
      right = middle;
      // We are looking for the lowest index so we can't return immediately.
      found = !pareResult;
    }
  }
  // left is the index if found, or the insertion point otherwise.
  // ~left is a shorthand for -left - 1.
  return found ? left : ~left;
};

Usage is binaryInsert(array, value). This also maintains the sort of the array.

Deleted my other answer because I missed the fact that the array is sorted.

The algorithm you wrote goes through every element in the array and if there are no matches appends the new element on the end. I assume this means you are running another sort after.

The whole algorithm could be improved by using a divide and conquer algorithm. Choose an element in the middle of the array, pare with new element and continue until you find the spot where to insert. It will be slightly faster than your above algorithm, and won't require a sort afterwards.

If you need help working out the algorithm, feel free to ask.

I've created a (simple and inplete) Set type before like this:

var Set = function (hashCodeGenerator) {
    this.hashCode = hashCodeGenerator;
    this.set = {};
    this.elements = [];
};
Set.prototype = {
  add: function (element) {
    var hashCode = this.hashCode(element);
    if (this.set[hashCode]) return false;
    this.set[hashCode] = true;
    this.elements.push(element);
    return true;
  },
  get: function (element) {
    var hashCode = this.hashCode(element);
    return this.set[hashCode];
  },
  getElements: function () { return this.elements; }
};

You just need to find out a good hashCodeGenerator function for your objects. If your objects are primitives, this function can return the object itself. You can then access the set elements in array form from the getElements accessor. Inserts are O(1). Space requirements are O(2n).

If your array is a binary tree, you can insert in O(log n) by putting the new element on the end and bubbling it up into place. Checks for duplicates would also take O(log n) to perform.

Wikipedia has a great explanation.