CODEWITHSUNDEEP
algorithm
Ray
Ray

Reputation: 2508

global max of local mins of k contiguous elements

If this question appears to be a replicate, please point it out.

The problem states:

Given an array of n elements and an integer k <= n, find the max of {min{a_i+1 ... a_i+k} for i in {0 ... n-k}}, i.e. find the max of the mins of k contiguous numbers.

For example, let the sequence a = {10, 21, 11, 13, 16, 15, 12, 9} and k = 3. The max is 13 for block {13, 16, 15}.

Hopefully the problem is clear!

It is straight forward to have a simple "brute force" making it O(nk). I am wondering if we can do it in O(nlogn) with "divide and conquer" or even in O(n) possibly with "dynamic programming".

It appears to me that if I try "divide and conquer", I have to deal with a set of blocks that is just across the middle border. Yet figuring out the max in that case seems to take O(k2), making the whole recurrence O(nk) again. (Maybe I get the numbers wrong somewhere!)

Looking for directions from you guys! Words and pseudocode are welcome!

Upvotes: 2

Views: 85

Answers (2)

Paul Hankin
Paul Hankin

Reputation: 58261

Here's one way to solve it using a dynamic programming-like solution. We construct an array "ys" that stores the mins of ever increasing ranges. It uses the idea that if the ys currently store mins of ranges of length p, then if we do for all i: ys[i] = min(ys[i], ys[i+p]), then we've now got mins of ranges of length 2p. Similarly, if we do ys[i] = min(ys[i], ys[i+p], xs[i+2p]) then we've got mins of ranges of length 2p+1. By using a technique very like exponentiation-by-squaring, we can end up with ys storing min-ranges of length k.

def mins(xs, k, ys):
    if k == 1: return ys
    mins(xs, k // 2, ys)
    for i in xrange(len(ys)):
        if i + k//2 < len(ys): ys[i] = min(ys[i], ys[i+k//2])
        if k % 2:
            if i+k-1 < len(ys): ys[i] = min(ys[i], xs[i+k-1])
    return ys

def maxmin(xs, k):
    return max(mins(xs, k, xs[:]))

We call mins recursively log_2(k) times, and otherwise we iterate over the ys array once per call. Thus, the algorithm is O(n log k).

Upvotes: 1

Dennis Meng
Dennis Meng

Reputation: 5187

You can do it in O(n log k) time; I'll start you off with a tip.

Suppose you have elements ai+1, ..., ai+k in some data structure with logarithmic time insert and constant time min operations (like a min heap). Can you use that to get the same data structure, but with elements ai+2, ..., ai+k+1 in O(log k) time?

Once you have that, then you can basically go through all of the consecutive groups of k and take the maximum of the minimums normally.

Upvotes: 1

Related Questions