Home » Interview coding problems/challenges

Range Minimum Query

Here, we are going to learn about the solution of range minimum query and its C++ implementation.
Submitted by Divyansh Jaipuriyar, on August 16, 2020

Problem statement

You are given a list of N numbers and Q queries. Each query is specified by two numbers i and j; the answer to each query is the minimum number between the range [i, j] (inclusive). 

Note: The query ranges are specified using 0-based indexing.

Problem description

The given problem asks you to find the minimum value in given range for each query [l,r] but the main catch here is time complexity, for each query if we are traversing the whole array then we will face time limit exceeded so we have to think of some data structure which can minimize this case hence we think of segment tree DS.

Input

The first line contains N, the number of integers in our list (N <= 100,000). The next line holds N numbers that are guaranteed to fit inside an integer. Following the list is a number Q (Q <= 10,000). The next Q lines each contain two numbers i and j which specify a query you must answer (0 <= i, j <= N-1).

Output

For each query, output the answer to that query on its own line in the order the queries were made.

Examples

Input:
N=5
[5,9,2,3,1]
q=3
1 3
0 3
2 4

Output:
2 
2 
2 
As 2 is the minimum element in the array 
for above for query range (1,3),
for query range (0,3) and for query range (2,4) respectively.

Input:
N=5
[5 -4 3 2 -1]
q=3
0 3
2 4
0 0

Output:
-4 
-1 
5 
As according to their index range these are the respective 
smallest elements in the range for (0,3),(2,4) and (0,0) respectively.

Solution Approach

Brute Force Approach:

The brute force approach, in this problem can be used if the time constraint is not very strict, in this approach we will iterate the range[l,r] for each query. Hence in the worst case, we have to travel all elements of the array for each query. For each query, We will initialize the answer with maximum value and iterate through the range and assign minimum values to it of that range.

Time Complexity for the above approach in the worst case is: O(n*q) which is huge.

Space Complexity for the above approach is: O(1)

Segment Tree Approach:

Segment Tree is basically a binary tree used for storing the intervals or segments. Each node in the Segment Tree represents an interval.

A segment tree for a set I of n intervals uses O(n log n) storage and can be built in O(n log n) time. Segment trees support searching for all the intervals that contain a query point in O(log n + k), k being the number of retrieved intervals or segments.

Consider an array A of size N and segment tree ST.

The root of ST will represent the whole array A[0:N-1], the leaf represents each array element and the in-between nodes of ST represent the range inside the whole array.
Segment tree provides two operations:

Update and Query operation.

Update to update element in an array an change the correspondence in the segment tree.

Query to obtain the answer for the given query range.

update: Given some index id and some value val, so you change arr[id]=val.

Query: Given some range l and r you need to find min in the range[l,r].

In this problem, we will build a segment tree ST with build function and also build a query function that will return the minimum element in the given range.

Here si is the index of segment tree, st is the segment tree node starting index

We create an array for storing elements and array for segment tree, the build function will be responsible for building the tree, we check if we are at root node that is when start and end value of the node is same, then we assign node value to start index of the array.

Otherwise, we find the middle index of the range and call recursively for building the left side of the segment tree and right side of the segment tree and then update the current node with the left and right side of the tree node.

For the query function it will have five parameter segment index, starting index of range and ending index of range, query start index and query end index, if the query index range is out of bound then we return appropriately according to our need as for finding minimum value in query range we return INT_MAX value and for maximum value, we return INT_MIN so that it does not affect our final values.

Time Complexity for the above approach in the worst case is: O(Q*log(n))

Space Complexity for the above approach in the worst case is: O(n)

C++ Implementation (Recursion)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;

ll arr[100005];

int main()
{
    cout << "Enter size of array: ";
    ll n;
    cin >> n;
    
    cout << "Enter array elements: ";
    for (ll i = 0; i < n; i++)
        cin >> arr[i];
    
    ll q;
    
    cout << "Enter query size: ";
    cin >> q;
    
    ll x, y, ans;
    
    while (q--) {
        cout << "Enter left and right index: ";
        cin >> x >> y;
    
        //initialize ans with maximum values.
        ans = INT_MAX;
    
        //iterate through the range.
        for (ll i = x; i <= y; i++)
            ans = min(ans, arr[i]);
    
        cout << "Minimum value: ";
        cout << ans << "\n";
    }
    
    return 0;
}

Output

Enter size of array: 3
Enter array elements: 1 4 1
Enter query size: 2
Enter left and right index: 1 1
Minimum value: 4
Enter left and right index: 1 2
Minimum value: 1

C++ Implementation (Segment Tree Approach)

#include <bits/stdc++.h>
using namespace std;

typedef long long ll;
//array to store array elements
ll arr[100005];

//ST is our segment tree.
ll ST[4 * 100005];

//build function to construct ST.
void build(ll si, ll st, ll en)
{
    //if start is equal to end(single size node).
    if (st == en) {
        //leaf node condition.
        ST[si] = arr[st];
        return;
    }

    //find mid index.
    ll mid = st + (en - st) / 2;

    //recursively build left child.
    build(2 * si, st, mid);

    //recursively build right child.
    build(2 * si + 1, mid + 1, en);

    //current node is formed
    //from left and right nodes.
    ST[si] = min(ST[2 * si], ST[2 * si + 1]);

    return;
}

//query function that return.
ll query(ll si, ll st, ll en, ll qs, ll qe)
{
    //segment range is out of query range.
    if (st > qe || en < qs)
        return INT_MAX;
 
    //if segment range is under query range.
    if (st >= qs and en <= qe)
        return ST[si];

    //find mid index.
    ll mid = st + (en - st) / 2;

    //return minimum element from left
    //right recursive calls.
    return min(query(2 * si, st, mid, qs, qe), query(2 * si + 1, mid + 1, en, qs, qe));
}

//main function.
int main()
{
    //declare size of input array.
    cout << "Enter size of array: ";
    ll n;
    cin >> n;

    //take input elements.
    cout << "Enter elements: ";
    for (ll i = 1; i <= n; i++)
        cin >> arr[i];

    //call build function to construct ST.
    build(1, 1, n);

    ll q;

    cout << "Enter size of queries: ";
    cin >> q;

    while (q--) {
        //take input range.
        ll x, y;
        cout << "Enter range indices: ";
        cin >> x >> y;
    
        x++; //increment x and y.
        y++; //because of 0 based index.
    
        cout << query(1, 1, n, x, y) << "\n";
    }
    
    return 0;
}

Output

Enter size of array: 5
Enter elements: 5 -4 3 2 -1
Enter size of queries: 3
Enter range indices: 0 3
-4
Enter range indices: 2 4
-1
Enter range indices: 0 0
5