Imagine that we have an array like structure A with n elements all of which are initially 0. ($A[i]=0$)

What is a data structure that supports the following operations:

1) Given an element A[i]=0 set A[i] to 1 in O(1) worst case

2) Given the index i return A[i] in O(1) worst case

3) Given the index i retrun the smallest $j\geq i$ such that $A[j]=0$ or $-1$ if there is no such index in amortized time as small as possible

Obviously an array supports the first 2. It doesnt not support 3). How to modify it?

  • $\begingroup$ Can you only set entries from 0 to 1 or can you also set entries from x to 0? $\endgroup$
    – G. Bach
    Dec 5 '13 at 2:03
  • $\begingroup$ Only from 0 to 1 $\endgroup$
    – user35202
    Dec 5 '13 at 4:00
  • $\begingroup$ Yes, this is a nice homework exercise. What have you tried? What's the simplest technique you can think of to avoid repeating work? We expect you to make a serious effort on your own before asking here, and to show us what you've tried. $\endgroup$
    – D.W.
    Dec 6 '13 at 1:08

At every index of the array you should store an extra detail of the immediate index that contains a "0". Updating this index in an amortised complexity of O(1) will give the solution.

Suppose you are updating the extra detail at an index i and the immediate 0 is found at j. Then, the extra detail will have the value j for all the values between i & j.

Now the amortised cost for every operation will be O(1) for updating and retrieving the stored index is O(1).


Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.