Find Maximum element in a given range of unsorted array [Preprocessing Allowed]?

Question

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.

Answer 1

Solutions:

I have found three solutions, each useful under certain conditions. They are:

1. Build a matrix (my original solution)
2. Build a binary tree
3. Do not preprocess

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(n²/log n) queries and have at least O(n²) 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],
• etc.

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(n²/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
  }
}

Answer 2

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])