Approach to remove element from array in O(1)

Question

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?

It is not possible to remove an element from an array in O(1) time. — Pointy, Aug 09 '19 at 12:39
@nickzoum _For design purposes, It must be without modifying original array,_ I think that's the main issue. So, if I understood the real issue, you need to create a **new array** out of the existing one by filtering some elements? is that it? — briosheje, Aug 09 '19 at 12:40
I'm voting to close this question as off-topic because the request is impossible to satisfy. — Pointy, Aug 09 '19 at 12:40
@Pointy, doesn't `[...arr.slice(0, i), ...arr.slice(i + 1, arr.length - 1)]` removes in O(1)? — guijob, Aug 09 '19 at 12:42
To create the new array, the elements of the old array have to be traversed; you have to copy each value (except the one you don't want) into the new array. That's O(n). — Pointy, Aug 09 '19 at 12:42
@briosheje, yeah. I already know which element I will remove from this array, so I need a new one without this element only — guijob, Aug 09 '19 at 12:44
"In C, I could create this structure using point[er]s". Somehow, I doubt it. Your requirements seem inconsistent. But, perhaps I misunderstand what you are driving at. If you do have a C-implementation of a data structure, put it in your question and ask how you could get similar functionality with JS. — John Coleman, Aug 09 '19 at 12:44
@guijob I'm sorry but, as long as you need to preserve the original array, I don't think you can do that in `O(1)`, because you still would need to traverse the array if you need to filter items out. Morever, you mention that the original array shouldn't be modified: in your current approach, either slicing either filtering still keeps the "references" to the old array so, if you somehow alter the new array, the old one will be altered as well, which is something you should take care about as well. As a side note, you couldn't do that in C either, not in this way, at least... — briosheje, Aug 09 '19 at 12:49
I think I was misunderstood. I edited my question. I just want a new array without that element, not a deep copy without chosen element. — guijob, Aug 09 '19 at 12:51
Honestly the `.filter()` code is as good as you're going to get. Unless you're doing this a billion times a second it isn't going to matter, and if you *are* doing that then your overall data structures and algorithms should be revisited. — Pointy, Aug 09 '19 at 12:54
[This question](https://stackoverflow.com/q/18052959/4996248) asks your question in a more language-neutral way. Some of the answers might help. — John Coleman, Aug 09 '19 at 12:56
@JohnColeman, thanks for this reference. In this case OP wants search and delete operations in O(1). I just want delete operation in O(1). — guijob, Aug 09 '19 at 13:03
Perhaps you could take an errata approach and maintain a set of "deleted" items (without actually deleting them) and add to the errata in `O(1)` time. Refactor your code so that when it processes an element in the array, it checks if it is deleted or not. If only a few items are to be removed, this might not degrade the performance of the array much. — John Coleman, Aug 09 '19 at 13:09
@guijob if you want a new array after the delete, can you explain how that can possibly come into existence without it being an O(n) process? — Pointy, Aug 09 '19 at 13:28
Edited question removing the requirement of being new array as it is impossible in O(1) — guijob, Aug 09 '19 at 14:08

StepUp · Answer 1 · 2021-06-16T07:23:25.393

3

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

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
Remove is O(N) because array is shifted
Remove by index is O(N) as it is necessary to shift elements at higher indices
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.

edited Jun 16 '21 at 07:23

answered Aug 09 '19 at 14:08

StepUp

36,391
15
88
148

1

thank you. certainly an array isn't a good data structure for this kind of problem. – guijob Aug 09 '19 at 14:15
Man, two questions: 1) Are you sure about adding item being `O(n)`? I'm asking because this doesn't seems so logical. 2) Does `Map.delete()` has `O(1)`? – guijob Aug 09 '19 at 14:22
@guijob https://stackoverflow.com/questions/31091772/javascript-es6-computational-time-complexity-of-collections – StepUp Aug 09 '19 at 14:58
1

push to the array is O(1), its just put new item at the end of the array and update its size – Filip Kováč Jun 16 '21 at 07:07
@FilipKováč yeah, you are right! Thanks for your great comment! I've edited my reply! :) – StepUp Jun 16 '21 at 07:24

score 0 · Answer 2 · answered Jul 31 '21 at 18:43

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());

Approach to remove element from array in O(1)

2 Answers2