Lowest value in range

Question

I would like to find the lowest value in some range.
Do I have to iterate array each time or is there any dynamic method?

Lets say I have input array:

index: 0 1 2 3 4 5 6 7
value: 1 4 6 1 6 7 2 3

and then I have to choose smallest in range < a,b > (inclusive). For example:

min(0,7) = 1
min(0,2) = 1
min(4,6) = 2
min(1,2) = 4

Im interested in the fastest solution, it would be the best to get the results in constant time.

Array won't be changed in meantime.

Answer 1

If you are going to perform multiple queries over the same set of numbers then you will want to construct a Cartesian Tree.

Cartesian trees may be used as part of an efficient data structure for range minimum queries, a range searching problem involving queries that ask for the minimum value in a contiguous subsequence of the original sequence.

As the article says, the queries can be performed in constant time.

Answer 2

You can use segment tree for this question. This is one of the best tutorial on segment tree and range minimum query.

I am giving JAVA implementation and the code is self explanatory, please let me know if you have any doubts.

public class SegmentTree {

    private int[] array;
    private int length;

    public static SegmentTree initialize(int[] a) {
        return new SegmentTree(a);
    }

    private SegmentTree(int[] a) {
        length = a.length - 1;
        int l = (int) (Math.log(a.length) / Math.log(2));
        l = (int) (Math.pow(2, l + 1) * 2 - 1);
        array = new int[l];
        initialize(a, 0, a.length - 1, 0);
    }

    private int initialize(int[] a, int p, int r, int index) {
        if (p == r) {
            array[index] = a[p];
            return a[p];
        }
        int q = p + (r - p) / 2;
        array[index] = Math.min(initialize(a, p, q, 2 * index + 1), initialize(a, q + 1, r, 2 * index + 2));
        return array[index];
    }

    public int findMin(int p, int r) {
        return _findMin(p, r, 0, length, 0);
    }

    private int _findMin(int qs, int qe, int ss, int se, int i) {
        if (qs <= ss && se <= qe) {
            return array[i];
        }
        if (qs > se || qe < ss) {
            return Integer.MAX_VALUE;
        }
        int q = ss + (se - ss) / 2;
        return Math.min(_findMin(qs, qe, ss, q, 2 * i + 1), _findMin(qs, qe, q + 1, se, 2 * i + 2));
    }

    private void print() {
        int index = 0;
        for (int k : array) {
            System.out.println(index + ":" + k);
            index++;
        }
    }

    public static void main(String[] args) {
        int[] a = {1, 34, 5, 6, 78, 5, 67, 89};
        SegmentTree s = initialize(a);
        System.out.println(s.findMin(2, 4));
    }
}

Answer 3

This is a standard task. You can use std library functionality. It should be the fastest possible. The example from here:

#include <iostream>     // std::cout
#include <algorithm>    // std::min_element, std::max_element

int main () {
  int myints[] = {3,7,2,5,6,4,9};

  std::cout << "The smallest element is " << *std::min_element(myints,myints+7) << '\n';

  return 0;
}

---

P.S. You can not get result in constant time, since if you need minimum between N elements you need to check each element. Minimum task complexity is O(N).

Answer 4

You can try the following (not sure if I am missing something)

If you are allowed some preprocessing, then you can have an array of local minima( valleys ).

This array shall be sorted as per the respective indices.

Once you get an interval, perform a binary search of the lower index in the minima array. Choose the greater one in that array. say I1

Then perform a binary search of the higher given index in the minima array. Choose the smaller one in that array. say I2

If I2 >= I1, then atleast one local minimum exists in the interval. Just compare values at the minima in that interval and at the boundaries to get the answer.

Else, no local minimum exists in the interval. In this case, the minimum shall be at the boundary of the interval. Just compare the two values and get the lower one.