Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem statement
3.
Approach
4.
 
5.
 
6.
 
7.
 
8.
 
9.
Code
10.
 
11.
 
12.
Complexity analysis
13.
FAQs
14.
Key Takeaways
Last Updated: Mar 27, 2024

Range Min Using Sparse Table

Author Malay Gain
2 upvotes

Introduction

Sparse Table is a special kind of Data Structure to answer range queries on an array efficiently. But there is a limitation as the sparse table can be used only on static data set i.e. array should not be updated between two queries. As the title of this article suggests we will discuss the construction of a sparse table in the context of a min query.

Here first, we will first describe how the sparse table is represented and then we will solve the range min query problem using the sparse table.

Recommended Topic, Array Implementation of Queue and  Rabin Karp Algorithm

Problem statement

There is an array of integers. You are given some queries of ranges. For each query, you need to find the minimum integer of the range from the given array.

Input

 arr[ ] = { 2, 4, 3, 5, 7, 9 } 
 range=[0,2]

Output

 2

Explanation

Range min = min(2,4,3)=2

 

Note: Please try to solve the problem first and then see the below solution approach.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Approach

As the title of this article itself suggests we will be using the concept of a sparse table to solve the problem. Let’s first see how a sparse table is constructed from a given array.

Construction of Sparse Table

The main intuition behind sparse table representation comes from the binary representation of an integer. As any integer can have its unique binary representation, it can be expressed as the sum of powers of 2. So, any interval or range can be expressed as the sum of decreasing powers of 2.

We will precompute the minimum of the ranges having the length of a power of 2 from each index of the given array. To answer queries efficiently we will use these precomputed values.

To store these precomputed values we will use a 2D array known as the sparse table of size n*(k+1) where n is the length of the given array and k=logn (of base 2).

For any sparse table st, st[i][j] will store the minimum of the range [ i to  i+2j-1] that is of length 2j.

range [i,  i+2j-1] can be broken into two ranges [i, i+2j-1-1] and [ i+2j-1,  i+2j-1] of length  2j-1.So, st[i][j] can be expressed as 
st[ i][ j] = min(st[ i ][ j-1] ,  st[ i+2j-1] [  j-1])

//constructing the sparse table

int st[n][k+1];

for(int i=0;i<n;i++)
{
  st[i][0]=arr[i];
}

for(int j=1;j<=k;j++)
{
	for(int i=0;i<n;i++)
	{
  	st[i][j] = min(st[i][j-1] , st[ i+1<<(j-1)][j-1]);
	}
}

For answering the given range min query [l,r] we will try to split the range into lengths of powers of 2 starting from the largest possible value k. If the first split is the range [l, l+2j-1] i.e. st[ l, j], we will consider the remaining range [r-2j +1, r] i.e.

st[r-2j +1, j].

//answering range min query (l,r)
int    query(int l,int r)
{
  int minimum=INT_MAX;
  int j=log(r-l+1)/log(2);

  minimum=min(st[ l][ j], st[r-(1<<j)+1][ j]);


 return minimum;
}    

 

 

 

 

 

 

Code

//C++ implementation of constrcuting Sparse Table 

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

//driver code

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



	//constructing Sparse Table
	int k=log(n)/log(2);

	int st[n][k+1];

	for(int i=0;i<n;i++)
	{
	 st[i][0]=arr[i];
	}

	for(int j=1;j<=k;j++)
	{
		for(int i=0;i<n;i++)
		{
  		st[i][j] = min( st[i][j-1] , st[ i+1<<(j-1)][j-1] );
		}
	}

	//answering query (l,r)
    	int l=0,r=2;
    	
	int minimum=INT_MAX;
	int j=log(r-l+1)/log(2);

	minimum=min(st[l][j],st[r-(1<<j)+1][j]);


	cout<<" min of the given range for the given query: "<<minimum;
}

Output

min of the given range for the given query: 2

 

 

Complexity analysis

The Time Complexity of constructing a sparse table is O(n*k) ≅ O(n*logn) and answering a single query takes O(1)where n is the size of the given array.

Space complexity is O(n*logn).

FAQs

  1. What is the Sparse Table?
    Sparse Table is a special kind of data structure to answer range queries on an array efficiently. It is implemented as a 2d array.
     
  2. In which type of problem Sparse Table can be used?
    To perform range queries on any static data set, the sparse table is used.

Key Takeaways

This article covered the construction of a sparse table and how to find min range using the sparse table.

Also, check out the article on the range sum using sparse table to clear the concepts about sparse table data structure.
Side by side, you can also practice a wide variety of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, you can also find the interview experience of scholars working in renowned product-based companies here. 

Happy learning!

Previous article
Sparse Table Construction (SUM QRY)
Next article
Range GCD Query Using Sparse Table
Live masterclass