2
$\begingroup$

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?

Improve this question
$\endgroup$
3
  • $\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, 2013 at 2:03
  • $\begingroup$ Only from 0 to 1 $\endgroup$
    – user35202
    Dec 5, 2013 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, 2013 at 1:08

1 Answer 1

Reset to default
2
$\begingroup$

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).

Improve this answer
$\endgroup$

Your Answer

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

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