Priority Queue is a wonderful Data Structure having a wide range of applications and is implemented using Heap Data Structure. Numerous amounts of problems are based on the concepts of priority queues. It is an important Data Structure when it comes to technical interviews of top tech companies as well. In this article, we will cover one such problem.
Problem statement
You are given an array of intervals[] consisting of n pairs of integers where each pair is denoting a range[l, r], also given an arrayQ[]consisting of m integers. For each integer, the task is to find the size of the smallest interval that contains that element. Return-1 if no valid interval exists.
Note: Please try to solve the problem first and then see the below solution approach.
Approaches
This problem can be solved mainly in two ways. Let’s see the approaches.
Brute Force approach
First, we will iterate through the Q[ ] array, and for each of its elements, we will maintain a variable, min_range, and iterate through the array of intervals[ ]; if the element exists in any of the intervals and the size of the interval is less than previous valid intervals we will update min_range with the size of this interval. After examining each interval, we will store the min_range value of the element in an array of ans[ ] and if no such interval exists, we will store -1 for that element.
Code
// C++ implementation of brute force approach
#include<bits/stdc++.h>
using namespace std;
// function for finding min intervals
vector<int> min_range(vector<vector<int>> intervals,vector<int> Q)
{
vector<int> ans(Q.size(),-1);
//iterating through the Q[] array
for(int i=0;i<Q.size();i++)
{
int min_range=INT_MAX;
int flag=-1;
// iterating through the array of intervals[]
for(int j=0;j<intervals.size();j++)
{
//if the element exists in any of the intervals and
//the size of the interval is less than previous valid intervals we will update min_range
if(Q[i]>=intervals[j][0] && Q[i]<=intervals[j][1] && min_range>intervals[j][1]-intervals[j][0]+1 )
{
min_range=intervals[j][1]-intervals[j][0]+1;
flag=0;
}
}
if(!flag)
{
ans[i]=min_range;
}
}
return ans;
}
// driver code
int main()
{
vector<vector<int>> intervals{ { 9, 27 },{ 1, 3 },{ 1, 4 }, { 3, 6 }, { 7, 17 } };
vector<int> Q = { 6, 15, 2, 30 };
vector<int> ans = min_range(intervals, Q);
// printing the final result for each element of Q
for (int i = 0; i < ans.size(); i++) {
cout << ans[i] << " ";
}
return 0;
}
Output
4 11 3 -1
Complexity
The above approach takes O(n*m) time where n is the size of the intervals array and m is the size of Q[ ] array.
In this approach, we will use a priority queue to find the minimum range for any particular element optimally.
Code
// C++ implementation of optimal approach
#include<bits/stdc++.h>
using namespace std;
// function for finding min intervals
vector<int> min_interval(vector<vector<int>> intervals,vector<int> Q)
{
// storing all the Queries
// along with its index
vector<vector<int> > Queries;
for (int i = 0; i < Q.size(); i++)
{
Queries.push_back({ Q[i], i });
}
// sorting the intervals and Queries
sort(intervals.begin(), intervals.end());
sort(Queries.begin(), Queries.end());
// max priority queue to keep track
// of intervals size and right value
priority_queue<vector<int> > pq;
// for storing the result of all the queries
vector<int> ans(Q.size(), -1);
// current position of intervals
int i = 0;
//interating through the quries
for (int j = 0; j < Queries.size(); j++)
{
int temp = Queries[j][0]; // the current query
// storing all the intervals whose left value is less than or equal to the current query
while (intervals[i][0] <= temp && i < intervals.size() )
{
// storing the negative value of range size(so that minimum interval will be on top) and
// the right bound of the interval
pq.push({ intervals[i][0] -intervals[i][1] -1,intervals[i++][1] });
}
// removing all the intervals with right value less than the current query
// as it will not valid for next quries also
while (!pq.empty() && temp > pq.top()[1]) {
pq.pop();
}
// if the valid interval exists
// and store the ans
if (!pq.empty())
ans[Queries[j][1]] = -pq.top()[0];
}
return ans;
}
// driver code
int main()
{
vector<vector<int>> intervals{ { 9, 27 },{ 1, 3 },{ 1, 4 }, { 3, 6 }, { 7, 17 } };
vector<int> Q = { 6, 15, 2, 30 };
vector<int> ans = min_interval(intervals, Q);
// printing the final result for each elements of Q
for (int i = 0; i < ans.size(); i++)
cout << ans[i] << " ";
return 0;
}
Output
4 11 3 -1
Complexity
The above approach takes O(nlogn + mlogm) time where n is the size of the intervals array and m is the size of Q[ ] array.
Space complexity is O(n+m) for the priority queue and the result array.
Frequently Asked Questions
What is a priority queue?
It is a special kind of queue where each element has its own priority and elements are served (popped out) according to this priority.
How to implement min-heap using the C++ STL library?
In C++, STL library priority_queue is by default made max-heap. To use priority_queue as min-heap, we need to add two extra arguments as shown below.
This article covered how to find the minimum range size that contains the given element for Q queries.
Check out the Coding Ninjas Studio library for getting a better hold of the data structures and algorithms.
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.
305+ registered