Take the 2-minute tour ×
Programmers Stack Exchange is a question and answer site for professional programmers interested in conceptual questions about software development. It's 100% free, no registration required.

I have an unsorted array. I have queries in which I give a range and then the maximum value from that range has to returned. For example:

array[]={23,17,9,45,78,2,4,6,90,1};
query(both inclusive): 2 6
answer: 78

Which algorithm or data structure do I construct to quickly retrieve maximum value from any range. (There are a lot of queries)

EDIT: This is indeed a simple version of the actual problem. I can have the array size as large as 100000 and the number of queries upto 100000. So I definitely require some preprocessing which'll facilitate a fast query response.

share|improve this question
3  
Why is it unsorted? The problem is trivial if it's sorted, so the obvious approach is to sort it. –  delnan May 4 '13 at 9:41
    
@delnan Without some extra mechanism, you lose track of which values were originally in the range to be queried... –  Thijs van Dien May 4 '13 at 9:54
    
Specify your whole problem. If this knowledge (or any other information) matters, one has to know to factor that into the solution. –  delnan May 4 '13 at 9:56
1  
Am I missing something, or is this just a matter of visiting items 2 through 6 and finding the maximum value of those elements? –  Blrfl May 4 '13 at 17:27
    
@Blrfl: I don't think you're missing anything, except maybe the part about many queries. It's not really clear whether there's any point in building a structure that makes queries substantially cheaper than a sequential search. (Although there wouldn't be much point in asking the question here if that weren't the idea.) –  Mike Sherrill 'Cat Recall' May 4 '13 at 18:31

4 Answers 4

I think you could construct some kind of binary tree where each left child node contains the maximum value in the left half of the range covered by its parent and the child right node the maximum value in the right half.

            78           
     45            78     
  23    45     78      6  
23 17  9 45   78 2    4 6   

Then you only need to find a way to determine which nodes you minimally need to check to find the maximum value in the range queried. In this example, to get the maximum value in the index range [2, 6] you would have max(45, 78, 4) instead of max(9, 45, 78, 2, 4). As the tree grows, the gain will be larger.

share|improve this answer
1  
For this to work, there's information missing from your example tree: Each internal node must have both the maximum, and the total number of child nodes it has. Otherwise the search has no way of knowing that (for example) it doesn't have to look at all the children of 78 (and skip the 2), because for all it knows index 6 is in that subtree. –  Izkata May 4 '13 at 18:14
    
Otherwise, +1 as I find this rather inventive –  Izkata May 4 '13 at 18:16
    
+1: This is a powerful technique for answering queries about subranges of a list in log(N) time, usable whevever the data at the root node can be computed in constant time from the data at the children. –  kevin cline May 4 '13 at 19:40

To complement ngoaho91's answer.

The best way to solve this problem is using the Segment Tree data structure. This allows you to answer such queries in O(log(n)), that would mean the total complexity of your algorithm would be O(Q*logn) where Q is the number of queries. If you used the naive algorithm, the total complexity would be O(Q*n) which is obviouslly slower.

There is, however, a drawback of the usage of Segment Trees. It's the memory that ocuppy, but a lot of times you care more about memory than about speed.

I will briefly describe the algorithms used by this DS:

The segment tree is just an special case of a Binary Search Tree, where every node holds the value of the range it is assigned to. The root node, is assigned the range [0, n]. The left child is assigned the range [0, (0+n)/2] and the right child [(0+n)/2+1, n]. This way the tree will be built.

Create Tree:

/*
    A[] -> array of original values
    tree[] -> Segment Tree Data Structure.
    node -> the node we are actually in: remember left child is 2*node, right child is 2*node+1
    a, b -> The limits of the actual array. This is used because we are dealing
                with a recursive function.
*/

int tree[SIZE];

void build_tree(vector<int> A, int node, int a, int b) {
    if (a == b) { // We get to a simple element
        tree[node] = A[a]; // This node stores the only value
    }
    else {
        int leftChild, rightChild, middle;
        leftChild = 2*node;
        rightChild = 2*node+1; // Or leftChild+1
        middle = (a+b) / 2;
        build_tree(A, leftChild, a, middle); // Recursively build the tree in the left child
        build_tree(A, rightChild, middle+1, b); // Recursively build the tree in the right child

        tree[node] = max(tree[leftChild], tree[rightChild]); // The Value of the actual node, 
                                                            //is the max of both of the children.
    }
}

Query Tree

int query(int node, int a, int b, int p, int q) {
    if (b < p || a > q) // The actual range is outside this range
        return -INF; // Return a negative big number. Can you figure out why?
    else if (p >= a && b >= q) // Query inside the range
        return tree[node];
    int l, r, m;
    l = 2*node;
    r = l+1;
    m = (a+b) / 2;
    return max(query(l, a, m, p, q), query(r, m+1, b, p, q)); // Return the max of querying both children.
}

If you need further explanation, just let me know.

BTW, Segment Tree also supports update of a single element or a range of elements in O(log n)

share|improve this answer

The best algorithm would be in O(n) time as below let start, end be the index of the bounds of range

int findMax(int[] a, start, end) {
   max = Integer.MIN; // initialize to minimum Integer

   for(int i=start; i <= end; i++) 
      if ( a[i] > max )
         max = a[i];

   return max; 
}
share|improve this answer
2  
-1 for merely repeating the algorithm the OP was trying to improve on. –  kevin cline May 4 '13 at 19:42
    
+1 for posting a solution to the as-stated problem. This really is the only way to do it if you have an array and don't know what the bounds are going to be a priori. (Although I would initialize max to a[i] and start the for loop at i+1.) –  Blrfl May 4 '13 at 20:36
    
@kevincline It's not just restating - it's also saying "Yes, you already have the best algorithm for this task", with a minor improvement (jump to start, stop at end). And I agree, this is the best for a one-time lookup. @ThijsvanDien's answer is only better if the lookup is going to happen multiple times, since it takes longer to set up initially. –  Izkata May 6 '13 at 17:03
    
Granted, at the time of posting this answer, the question did not include the edit confirming that he'll be doing many queries over the same data. –  Izkata May 6 '13 at 18:44

try "segment tree" data structure
there are 2 step
build_tree() O(n)
query(int min, int max) O(nlogn)

http://en.wikipedia.org/wiki/Segment_tree

edit:

you guys just don't read the wiki i sent!

this algorithm is:
- you traverse the array 1 time to build tree. O(n)
- next 100000000+ times you want to know max of any part of array, just call the query function. O(logn) for every query
- c++ implement here geeksforgeeks.org/segment-tree-set-1-range-minimum-query/
old algorithm is:
every query, just traverse the selected area and find.

so, if you gonna use this algorithm to process once, OK, it slower than old way. but if you gonna process huge number of query(billion), it's very efficient you can generate text file like this, for test

line 1: 50000 random number from 0-1000000, split by '(space)'(it's the array)
line 2: 2 random number from 1 to 50000, split by '(space)'(it's the query)
...
line 200000: likes line 2, it's random query too

this is the example problem, sorry but this is in vietnamese
http://vn.spoj.com/problems/NKLINEUP/
if you solve it by old way, you never pass.

share|improve this answer
3  
I don't think that's relevant. An interval tree holds intervals, not integers, and the operations they permit look nothing like what OP asks for. You could, of course, generate all possible intervals and store them in an interval tree, but (1) there are exponentially many of them, so this doesn't scale, and (2) the operations still don't look like what OP asks for. –  delnan May 4 '13 at 10:15
    
my mistake, i mean segment tree, not interval tree. –  ngoaho91 May 4 '13 at 10:23
    
Interesting, I think I've never come across this tree! IIUC this still requires storing all possible intervals, though. I think there's O(n^2) of those, which is rather expensive. (Also, shouldn't query be O(log n + k) for k results? –  delnan May 4 '13 at 10:30
    
yes, void build_tree() must travel cross the array. and store max(or min) value for every nodes. but in many case, memory cost is not important than speed. –  ngoaho91 May 4 '13 at 10:43
2  
I can't imagine this being any faster than a plain O(n) search of the array, as described in tarun_telang's answer. First instinct is that O(log n + k) is faster than O(n), but the O(log n + k) is just retrieval of the sub-array - equivalent to O(1) array access given the start and end points. You would still need to traverse it to find the maximum. –  Izkata May 4 '13 at 17:53

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.