What is the fastest way to find the maximum element in the given range of unsorted array, if the preprocessing is allowed.
We have initial array A = {3, 2, 4, 5, 1} and we need to preprocess it, and then we answer the q queries.
Example for a query, if range specified in query is [0, 2], then the maximum element in this range is 4.
Solutions:
I have found three solutions, each useful under certain conditions. They are:
Each of these have advantages and disadvantages discussed below.
Matrix:
Summary:
Build a two-dimensional array M such that M[i][j] is the maximum element in A[i:j].
Analysis:
This option is best when you are doing more than O(n2/log n) queries and have at least O(n2) space.
Space requirement: O(n^2)
Preprocessing time: O(n^2)
Query time: O(1)
Pseudocode:
class Range {
private M
function Preprocess(A) {
for(i from 0 to n)
M[i][i] = A[i]
for(j from i+1 to n)
M[i][j] = max(M[i][j-1], A[j])
}
function Query(i, j) {
return M[i][j]
}
}
Binary tree:
Summary:
This is the most complex option. You build a tree T such that
T.root is the maximum value in A[0:n], T.root.left is the maximum value in A[0:n/2],T.root.right is the maximum value in A[n/2+1:n],Then there are at most O(log n) nodes representing the maximum values for any given range.
Analysis:
This option is best when either a) you are limited to O(n) space or b) you are doing fewer than O(n2/log n) queries.
Space requirement: O(n)
Preprocessing time: O(n)
Query time: O(log n)
Pseudocode:
class Range {
private T
function Preprocess(A) {
T = BinaryTree({leaves: A})
################################################
# loop over all levels of the tree,
# starting just above the leaves
################################################
foreach(T.levels as level)
foreach(level as node)
node.value = max(node.left.value, node.right.value)
node.leftBound = node.left.leftBound
node.rightBound = node.right.rightBound
}
function Query(i, j) {
nodes = []
currentLeft = T.root
currentRight = T.root
################################################
# search for the left bound of the range,
# keeping any nodes fully contained in the range
################################################
while(currentLeft.leftBound < i)
if(currentLeft.right.leftBound <= i)
currentLeft = currentLeft.right
else
# check if currentLeft.right is fully in the range
if(currentLeft.right.rightBound <= j)
nodes.push(currentLeft.right)
currentLeft = currentLeft.left
if(currentLeft.rightBound <= j)
nodes.push(currentLeft)
################################################
# repeat the above to find the right bound
################################################
while(currentRight.rightBound > j)
...
if(currentRight.leftBound >= i)
nodes.push(currentRight)
################################################
# find the maximum value in nodes
################################################
m = -inf
foreach(nodes as node)
m = max(m, node.value)
return m
}
}
(Note that the given pseudocode could potentially add a given node to nodes twice, causing redundant work. However, it will never add more than O(log n) nodes in total, and I didn't want to further complicate the pseudocode.)
Do not preprocess:
Summary:
If you aren't doing too many queries, you shouldn't waste time preprocessing.
Analysis:
This option is best when you will do very few queries (around O(1)).
Space requirement: O(n)
Preprocessing time: O(1)
Query time: O(n)
Pseudocode:
class Range {
private M
function Preprocess(A) {
M = A
}
function Query(i, j) {
m = M[i]
for(k = i+1; k < j; ++k)
m = max(m, M[k])
return m
}
}
Here's an implementation of the dynamic programming solution (O(n**2) preprocessing, O(1) for "max in range" query) from @Kittsil's answer. To find M[start][end] == max(A[start:end]) in Python:
#!/usr/bin/env python
A = [3, 2, 4, 5, 1]
n = len(A)
M = [[None] * (n + 1) for _ in range(n)]
for i in range(n):
for j in range(i, n):
M[i][j + 1] = A[j] if i == j else max(M[i][j], A[j])
Test:
for start in range(n):
for end in range(start + 1, n + 1):
assert M[start][end] == max(A[start:end])
