World's most popular travel blog for travel bloggers.

# [Solved]: array with a twist

, ,
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?

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