CODEWITHSUNDEEP
arraysalgorithmdata-structurestime-complexity
yobro97
yobro97

Reputation: 1145

Best approach for finding the maximum array element in a given range

Given a non-negative integer array of length n and m queries consisting of two integers a and b, it is expected to find the maximum in the range of index [a,b] of the array. Note that a can be greater than b, in which case the desired range is from a to n and then from 1 to b. And an input k is also given that signifies that the length of the range to be considered is also constant that is constant

Example: 

INPUT:
6 3 5 ---> n,m,k
7 6 2 6 1 5 ---> integer array
1 5 ---> query 1
2 6 ---> query 2
4 2 ---> query 3
OUTPUT:
7
6
7

I referred this article but am not able to get how to take care of the cases where a>b. Is there any other approach for this problem

Upvotes: 0

Views: 605

Answers (2)

Shridhar R Kulkarni
Shridhar R Kulkarni

Reputation: 7063

Sliding window approach:

To solve the problem using approach mentioned i.e. Sliding Window Maximum, Just append the input array to itself like as shown below:

7 6 2 6 1 5 7 6 2 6 1 5

For a<=b case work as normal.

For a>bcase: Consider b = a + k. So your new range is [a,a+k] which you can happily solve without any changes to algorithm.

To optimize the above approach a bit, you can just append first k elements.

If you slide over every time a query arrives, it takes O(n) per query. k being very close or equal to n is the worst case.

Alternative Approach: Use the following approach in case of heavy querying and flexible ranges.

You are looking for range queries and this is what Segment Trees are popular for.

This tutorial finds the minimum in given range. I know you have asked for maximum, which is just a trivial change you have to make in code.

For a>b case, query two times once for [1,b] & then for [a,n] and report the maximum out of the two.

Preprocessing time: O(n)

Extra Space: O(n)

This approach is very efficient as it will answer every query in O(logn) which is quite helpful in case you are querying too much.

Sliding Window is going to output maximum element in all the ranges, but you need the maximum element only in given range. So instead of going with Sliding Window approach go with Segment Trees or Binary Indexed Trees. You'll feel the fun of truly querying within a range and not sliding over. (Just sliding over every time a query arrives won't scale if the range is flexible.)

Upvotes: 1

zenwraight
zenwraight

Reputation: 2000

I think this could be done by using divide and conquer approach, so let's take a look at the above example.

So for the case a>b

find max for range (1,b), say max_b = max_in_range(1,b).
find max for range (a,n), say max_a = max_in_range(a,n).

Now you can easily take up max between two numbers using a in built max method in any language as

ans = max(max_a, max_b)

But problems like this which involes ranges, you can solve it using segment trees, here is the link to start with - https://en.wikipedia.org/wiki/Segment_tree

Hope this helps!

Upvotes: -2

Related Questions