2
$\begingroup$

I'm Telecommunication student so I don't have Computer Science background, just in case if my question looks stupid.

Here is my scenario:

  1. Consider an empty array named ARR with size N, we also have an array named MAP with size N that stores the state of ARR cells, ON for filled, OFF for empty, initially ARR is empty so every corresponding cell in MAP is set to OFF.

  2. we keep the next empty cell index in a variable named NEXT, initially since ARR is empty, NEXT is set to 0. NEXT always point to the first index i in the array MAP such that MAP[i] is OFF, if any exists.

  3. a function named add(element) always adds element into ARR at index NEXT, sets corresponding cell in MAP to ON.

  4. a function named insert(element, index) adds element into ARR at index specified by user, sets corresponding cell in MAP to ON.

  5. a function named delete(index) removes element from ARR at index specified by user, sets corresponding cell in MAP to OFF.

My question: How to update NEXT variable so it points to next empty cell index in ARR.

I know I can run a search on MAP from 0 to N and stop at the first occurrence of OFF and store its index as NEXT, but from what I read from online sources it has O(N) performance which is not great, I want to know if there are any better algorithms for this job or not, if not, can I design one myself? which books/online doc should I look into?

Thanks.

Improve this question
$\endgroup$
4
  • 1
    $\begingroup$ Just to be more precise: should NEXT always point to the first index $i$ in the array MAP such that MAP[i] is OFF, if any? $\endgroup$ Commented Jul 16, 2021 at 9:50
  • $\begingroup$ Hi Mehdi, welcome to cs.stackexchange.com. If the running time is not important for you , when you insert new element, with linear time checking you can find the first empty cell of the array. $\endgroup$ Commented Jul 16, 2021 at 10:01
  • $\begingroup$ @Steven yes, you got it correct, one of my friends suggested that NEXT itself could be an array to hold several indexes, but we weren't sure about the algorithm so I asked it here. $\endgroup$ Commented Jul 16, 2021 at 10:02
  • $\begingroup$ Or it's sufficient to set the next to be element that deleted from the array (according to $delete(index)$ procedure). Or when you call the procedure $Add(element)$ you can find the first cell that empty before inserted element or after it. Finally when you call $ insert(element, index)$, if $next=index$ you can act like that explained for procedure $Add(element)$. $\endgroup$ Commented Jul 16, 2021 at 10:07

1 Answer 1

Reset to default
2
$\begingroup$

I'm assuming that you're on a RAM machine with word size $\Theta(\log N$). Keep a van Emde Boas tree $T$ storing the empty positions (integers from $1$ to $N$).

Whenever you insert an element $i$, delete $i$ from $T$ (in $O(\log \log N$) time) and set NEXT to the minimum element in $T$ (in $O(1)$ time).

Whenever you delete an element $i$, insert $i$ to $T$ and set NEXT to the minimum between the current values of NEXT and $i$.

This requires $O(\log \log N)$ time per operation but would require time $O(N \log \log N)$ to build the tree. To improve the construction time to $O(N)$ you can start with a tree containing only the index $1$. Then during the first $N-1$ operations do the following: before the $i$-th operation is performed check if MAP[i+1]=OFF. If this is the case, then add $i+1$ to $T$. Proceed with the operation normally. This is taking advantage of the fact that, after the $i$-th operation is performed, we must necessarily have NEXT<=i+1.

You can't get much better solutions since you essentially need to solve the predecessor problem which admits a lower bound of $\Omega( \frac{\log \log N}{\log \log \log N})$ for a word size of $\Theta(\log N)$.

For a slower but easier to implement solution replace the van Emde Boas tree with an AVL tree. The initial tree can be built in $O(N)$ time (the keys are sorted) and each operation requires $O(\log N)$ time.

Improve this answer
$\endgroup$
2
  • $\begingroup$ Thanks for the solution, I'll try to implement it into code, I just have a question, $O(N \log \log N)$ to build the tree is juts a 1 time operation right? or per every add, insert, delete I should construct the tree? $\endgroup$ Commented Jul 16, 2021 at 11:13
  • $\begingroup$ The tree is constructed only once, at the same time when ARR and MAP are created and initialized. $\endgroup$ Commented Jul 16, 2021 at 11:24

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service and acknowledge you have read our privacy policy.

Start asking to get answers

Find the answer to your question by asking.

Ask question

Explore related questions

See similar questions with these tags.