Do you think IIT Guwahati certified course can help you in your career?
Introduction
I used to play a game called "Guess The Number" in my mid-childhood, in which you ask the player to pick a number from 1 to 50. Then you ask him a few questions such as, "What if the chosen number is less than or more than 30?". After a couple of questions, you told him his picked number.
I used to believe that was a brilliant way to pry knowledge out of someone's head back in the day. And it felt smart at the time, but now that I know Binary Search, all of my smartness has vanished.
In the actual world, there are many more binary search examples like the one above. Binary search is one of the algorithms that you should be very comfortable with. The problem we are going to discuss today is a variation of the binary search.
Let’s define the problem now.
Problem Statement
Given an array of ‘INTERVALS’, where ‘INTERVALS[x]’=[STARTx, ENDx] and all STARTx are unique.
The right interval for an interval ‘X’ is interval ‘Y’ if STARTy >= ENDx and STARTy are minimized.
You have to return an array RIGHT_INTERVALS where RIGHT_INTERVALS[X] = Right interval of interval ‘X’ which is -1 if no right interval of ‘X’ exists.
For example:
Now that we've defined th problem let's try to solve it.
The key question in the problem is, what is the right interval? If we observe closely, we can see we are just trying to find the lower bound for a number, i.e., END, in an array of ‘START’ intervals. And we can find the lower bound in an unsorted array by just traversing the array and finding the immediate next to the element. To sum up, we will traverse the array and find a lower bound for each interval.
Let's take a quick look at the algorithm.
Loop through the array of ‘INTERVALS’.
Find the lowest bound index for INTERVAL[i][1] (where 0 <= i < INTERVALS.size()).
To find the lower bound index, we iterate through the array and see if INTERVAL[j][0] (where 0 <= j < INTERVALS.size()) is greater than equal to INTERVAL[i][1], then we update our value of the lower bound index.
Next, we store the calculated index in the RIGHT_INTERVAL array.
Program
#include <iostream>
#include <vector>
#include <climits>
using namespace std;
// Function to find the right interval given an array of intervals.
vector<int> findRightInterval(vector<vector<int>> intervals)
{
// Size of array.
int n = intervals.size();
// Variables to keep track of lower bound.
int mn, index;
// If we have only one interval return [-1].
if (n == 1)
return {-1};
vector<int> rightInterval(n);
// Loop through the array of 'INTERVALS'.
for (int i = 0; i < n; i++)
{
mn = INT_MAX;
index = -1;
// For each interval find lower bound interval.
for (int j = 0; j < n; j++)
{
if (intervals[j][0] >= intervals[i][1])
{
if (mn > intervals[j][0])
{
mn = intervals[j][0];
index = j;
}
}
}
// Update the right interval index value.
rightInterval[i] = index;
}
// Return right interval array.
return rightInterval;
}
int main()
{
int n;
cout << "Enter the size of array N: ";
cin >> n;
vector<vector<int>> intervals(n, vector<int>(2));
cout << "Enter the intervals (START, END):\n";
for (int i = 0; i < n; i++)
{
cin >> intervals[i][0] >> intervals[i][1];
}
vector<int> rightIntervals = findRightInterval(intervals);
cout << "The array of right interval is: ";
cout << "[";
for (int i = 0; i < rightIntervals.size() - 1; i++) {
cout << rightIntervals[i] << ", ";
}
cout << rightIntervals[rightIntervals.size() - 1] << "]" << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Enter the size of array N: 5
Enter the intervals (START, END):
4 5
3 4
1 2
6 7
10 12
Output
The array of right interval is: [3, 0, 1, 4, -1]
Time Complexity
O(N^2), where 'N' is the size of the array 'INTERVALS'.
Since we are traversing 'N' elements for each 'N' element in the array.
Space Complexity
O(1), Since we are not using any extra space.
Approach 2-Sorting
One thing you should always consider while solving an array problem is if sorting can somehow reduce the algorithm's complexity. As we have seen in the previous approach, we have to find the lower bound of number in an unsorted array which took O(N) time, but if we sort the array, we can do it in O(log(N)) time using lower_bound STL function.
For example:
Let's discuss the algorithm briefly.
First we will create an array ‘VEC’ of pairs where VEC[i].first = INTERVALS[i][0] and VEC[i].second = i. We store the index because we need index after sorting.
Next, we sort the array ‘VEC’.
Now, we iterate over ‘INTERVALS’ and find the lower bound index using the lower_bound STL function next, we store the lower bound index value in the ‘RIGHT_INTERVAL’ array.
Program
#include <iostream>
#include <vector>
#include <algorithm>
using namespace std;
// Function that return lower bound index for a given 'KEY'.
int findLowerBoundIndex(vector<pair<int, int>> &vec, int key)
{
// Initialize the left and right pointer.
int left = 0, right = vec.size() - 1;
int mid;
// Loop until 'LEFT' is smaller than or equal to 'RIGHT'.
while (left <= right)
{
// Compute the 'MID' of array.
mid = (right + left) / 2;
// If 'LEFT' is equal to 'RIGHT', then if 'VEC[MID].first' is greater than or equal to the 'KEY', then return its index.
if (left == right)
{
if (vec[mid].first >= key)
return vec[mid].second;
// Else if 'KEY' is smaller than 'VEC[MID].first' then we have to check if it is the last element of 'VEC',
// in this case we return -1, else return 'VEC[MID + 1].second' i.e., next index.
if (mid + 1 < vec.size())
return vec[mid + 1].second;
return -1;
}
// If current value is equal to 'KEY', return its index.
if (vec[mid].first == key)
return vec[mid].second;
// Or else if current value is greater than 'KEY', update 'RIGHT'.
else if (vec[mid].first > key)
{
right = mid - 1;
}
// Else update 'LEFT'.
else
{
left = mid + 1;
}
}
return vec[mid].second;
}
// Function to find the right interval given an array of intervals.
vector<int> findRightInterval(vector<vector<int>> &intervals)
{
// Size of array.
int n = intervals.size();
// If we have only one interval return [-1].
if (n == 1)
return {-1};
vector<pair<int, int>> vec(n);
// Create a vector with 'START' and 'INDEX'.
for (int i = 0; i < n; i++)
{
vec[i] = make_pair(intervals[i][0], i);
}
// Sorting the array.
sort(vec.begin(), vec.end());
vector<int> rightInterval(n);
for (int i = 0; i < n; i++)
{
// Computer lower bound index for INTERVALS[i][1].
int lowerBoundIndex = findLowerBoundIndex
(vec, intervals[i][1]);
rightInterval[i] = lowerBoundIndex;
}
// Return the right intervals array.
return rightInterval;
}
int main()
{
int n;
cout << "Enter the size of array N: ";
cin >> n;
vector<vector<int>> intervals(n, vector<int>(2));
cout << "Enter the intervals (START, END):\n";
for (int i = 0; i < n; i++)
{
cin >> intervals[i][0] >> intervals[i][1];
}
vector<int> rightIntervals = findRightInterval(intervals);
cout << "The array of the right interval is: ";
cout << "[";
for (int i = 0; i < rightIntervals.size() - 1; i++) {
cout << rightIntervals[i] << ", ";
}
cout << rightIntervals[rightIntervals.size() - 1z] << "]" << endl;
return 0;
}
You can also try this code with Online C++ Compiler
In this section, we will try to implement the above approach using a map. Since the keys are sorted in a map, we don't have to sort the array explicitly. But Since insertion in map takes log(N) time and we are inserting ‘N’ elements time complexity of this approach is the same as the previous approach.
Now let's see how this will be implemented.
Create a map, ‘MP’ and store value such that keys are the start of intervals and value is the index of that interval.
Next, we loop through the array ‘INTERVALS’ and find lower bound using an inbuilt STL function of map lower_bound.
Program
#include <iostream>
#include <vector>
#include <map>
using namespace std;
// Function to find the right interval given an array of intervals.
vector<int> findRightInterval(vector<vector<int>> intervals)
{
// Size of array.
int n = intervals.size();
// If we have only one interval return [-1].
if (n == 1)
return {-1};
// Map to store the sorted list of intervals with 'START' as key and 'INDEX' as value.
map<int, int> mp;
for (int i = 0; i < n; i++)
{
mp[intervals[i][0]] = i;
}
vector<int> rightInterval(n);
for (int i = 0; i < n; i++)
{
// STL Function lower_bound returns lower bound interator for a key.
auto lowerBound = mp.lower_bound(intervals[i][1]);
// If lower bound does not exist, then store -1.
if (lowerBound == mp.end())
rightInterval[i] = -1;
// ELse store lower bound index.
else
rightInterval[i] = lowerBound->second;
}
// Return right interval array.
return rightInterval;
}
int main()
{
int n;
cout << "Enter the size of array N: ";
cin >> n;
vector<vector<int>> intervals(n, vector<int>(2));
cout << "Enter the intervals (START, END):\n";
for (int i = 0; i < n; i++)
{
cin >> intervals[i][0] >> intervals[i][1];
}
vector<int> rightIntervals = findRightInterval(intervals);
cout << "The array of the right interval is: ";
cout << "[";
for (int i = 0; i < rightIntervals.size() - 1; i++) {
cout << rightIntervals[i] << ", ";
}
cout << rightIntervals[rightIntervals.size() - 1] << "]" << endl;
return 0;
}
You can also try this code with Online C++ Compiler
Enter the size of array N: 5
Enter the intervals (START, END):
4 5
3 4
1 2
6 7
10 12
Output
The array of right interval is: [3, 0, 1, 4, -1]
Time Complexity
O(N*log(N)), where ‘N’ is the size of the ‘INTERVALS’ array.
Since we are creating a map of 'N' elements and each insertion takes log(N) time, the time complexity would be O(N * log(N)).
Also, the lower_bound() function takes log(N) time, and we are calling it 'N' times.
Hence the overall time complexity will be O(N*log(N)).
Space Complexity
O(N), Since we are creating a map of size ‘N’.
Key Takeaways
In the above blog, we learned how sorting could drastically improve time complexity.
If you have to find some value in an array somehow in your solution, then the best thing you can do before anything is sorting. After that, you can use binary search, which improves the complexity of the algorithm.
I hope you had fun reading this blog. Head over to Coding Ninjas Studio to read other such exciting blogs.
7+ registered 
