CODEWITHSUNDEEP
javascriptarraysperformance
guijob
guijob

Reputation: 4488

Approach to remove element from array in O(1)

I working with a really large array and I'm removing few elements from it. By now, every time I want to remove an element without knowing its index, I'm actually doing something like: 

const newarr = arr.filter(x => x !== y)

So, everytime I need to remove an element I'm running in O(n) complexity. I think worth creating an structure where I can remove an element from array in O(1) later.

For design purposes, it is an array of references and there aren't repeated elements.

I know I must somehow create an object with index as values and some convenient string as keys, so I can access index in O(1) and remove it using:

const newarr = [...arr.slice(0, i), ...arr.slice(i + 1, arr.length - 1)]

So, how to create this object? Is this a good approach?

Upvotes: 1

Views: 6669

Answers (3)

eurodoo Eurodoocom
eurodoo Eurodoocom

Reputation: 11

I think that everyone is probably aware, but I will write it again. In fact, deleting by index is O(1) in JS) If you don't care about the order... myarray[indexToDelete] = myarray[myarray.length - 1]; myarray.pop();

Upvotes: 0

Anonymous
Anonymous

Reputation: 1968

A bit late to the party, but I just came here from Google, so whoever else finds this thread, the most consize implementation of the O(1) queue that I have found so far is here. I just changed a couple of typos and switched to Map to maintain the order of properties. Live sample with tests.

Implementation

function Queue() {

  this.items = new Map();
  this.tail = 0;
  this.head = 0;

  this.enqueue = (e) => {
    this.items[this.tail++] = e;
  }

  this.dequeue = () => {
    if (this.tail === this.head) return null;
    let e = this.items[this.head];
    delete this.items[this.head++];
    return e;
  }
}

Tests

const queue = new Queue();

queue.enqueue("W");
queue.enqueue("A");
queue.enqueue("C");

console.log(queue.items)

for (let i in queue.items) {
    console.log('Iteration => ', i, ' => ', queue.items[i])
}

console.log('Expect W => ', queue.dequeue());
console.log('Expect A => ', queue.dequeue());
console.log('Expect C => ', queue.dequeue());

Upvotes: 0

StepUp
StepUp

Reputation: 38094

Let's see time complexities of some operations of array:

  1. Adding item is O(1). As insertion does not shift the index. It only adds a new index for the new item at the end of the array
  2. Remove is O(N) because array is shifted
  3. Remove by index is O(N) as it is necessary to shift elements at higher indices
  4. Remove an element at the end is O(1) because there is no shifting.

So you need to use another type of data structure to have O(1) of deletion.

Upvotes: 3

Related Questions