World's most popular travel blog for travel bloggers.

[Solved]: array with a twist

, , No Comments
Problem Detail: 

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?

Asked By : user35202

Answered By : b1tchacked

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

Best Answer from StackOverflow

Question Source :

3.2K people like this

 Download Related Notes/Documents


Post a Comment

Let us know your responses and feedback