CODEWITHSUNDEEP
algorithmlanguage-agnostic
DanielM
DanielM

Reputation: 1053

Sublinear algorithm to find the maximum contiguous range with elements >= k in an array

You are given an array A of length N containing natural numbers. The question is: Give an index i and a natural number k, what is the maximum offset m such that all elements in the subarray A[i,i+m] are greater or equal to k.

There is a trivial O(N) algorithm: Start at i and scan the array to the right until you hit an offset with A[i+m] < k.

What I am looking for is an algorithm and a datastructure such that:

Can anyone construct such an algorithm? Or is there a good argument why such an algorithm cannot exist?

The best thing I could come up with involves a O(N²) datastructure constructed in O(N²) and O(log N) lookup.

Upvotes: 0

Views: 172

Answers (1)

kraskevich
kraskevich

Reputation: 18556

Yes, it is possible. You can use a special data structure that can be constructed in linear time and answers a range maximum query in O(1). It is rather complex, you can read about it here. When we have this data structure, we can use binary search to find the largest feasible m. It requires O(log N) time per query.

Upvotes: 3

Related Questions