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.

Attwood

It seems like you need just for loop – Ditheism

And thats linear... Isn't it possible to go faster? – Attwood

You can precompute the result once for every possible range in O(N^2) time. After that, the lookup would be constant time. Depending on how often you need to look up over the same data, you may be able to amortize the initial cost. – Basidiospore

Values aren't sorted. Are you sure you can make any use of binsearch? – Attwood

@IgorTandetnik won't work for obvious reasons with arrays with 1 000 000 elements :/ – Attwood

@kittyPL - you can not do a binary search on an un-sorted range. – Gameto

@kitty: You are right. I was looking at the indexes. My bad – Rationalism

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.

Pharmacy

Nice structure, but I am not sure how the query can be perform in constant time. I would not have been surprised with a O(D) where D is the depth of the tree... but constant seems to be cutting it thin. In the original article, if I ask for the minimum in the range from 9 to 18 (which is 1), it seem to take more time that to determine that 10 was the minimum in [12,10,20,15]. – Jeneejenei

@MatthieuM.: It's tricky. The lookup involves finding the lowest common ancestor of the boundary nodes for the query in the tree. The simple implementation of that is O(D) as you expected, but there are tricks to find the LCA in O(1), see en.wikipedia.org/wiki/Lowest_common_ancestor – Pharmacy

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));
    }
}

Naivete

After reading the article the code became easy to understand. Still, naming variables qs, qe, ss, q isn't really good idea while explaining (I also like short names for simple functions). Also the comments would help alot. Anyway thanks for this logarithmic solution, +1 :) – Attwood

Answer 3

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.

Alveolus

Answer 4

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

Sip

Linear solution. I'm asking about something faster (if thats possible) – Attwood

Well. If there would be something faster it would be at std. – Sip

It depends. Maybe there is a dynamic solution. Those aren't common in std, afaik. – Attwood

Anyway It can't be faster than linear, you need to check each element at least ones. – Sip

Of course not. You can pre-generate some helper arrays and then use them to answer in shorter time. Read about prefix sums. en.wikipedia.org/wiki/Prefix_sum – Attwood