Code360 powered by Coding Ninjas X Code360 powered by Coding Ninjas X
Table of contents
Implementation in C++
Complexity Analysis
Frequently Asked Questions
Key Takeaways
Last Updated: Mar 27, 2024

Find the smallest range containing at least 1 element from given N ranges.

Author Urwashi Priya
0 upvote
Master Python: Predicting weather forecasts
Ashwin Goyal
Product Manager @


In this blog, we will discuss an array minimisation problem that has been asked frequently in Interviews. 

The problem is to Find the smallest range containing at least 1 element from given N ranges.

We are given N ranges, and our task is to search for the smallest range that contains at least 1 element from all the given ranges.

We need to find the minimum and a maximum number such that maximum-minimum is minimum and at least one number from each range should be in {minimum number, maximum number}. We need to choose the minimum number and maximum number as close as possible. Our minimum number should be as large as possible, and the maximum number should be as small as possible.

Example: Say, the ranges given are: {{1,6}, {2,7}, {3,8}, {4,9}}

Here all ranges contains 4.

So, our answer can be [4,4].

In this way, we need to find the most minimised answer.


The approach to Find the smallest range containing at least 1 element from given N ranges can be best solved by the greedy approach.

Best Time Complexity = n. Since the array will be traversed only once.

Declare two variables to store the starting and ending point of the range.

Calculate the smallest endpoint and largest starting point by looping over all the given ranges.

If the starting point is greater than the endpoint, print any integer between starting and ending points.

Else print the starting and ending points.


Time Complexity = n 

∵Time Complexity for traversing = n

Till now, I assume you have got the basic and conceptual idea of what has been asked in the problem statement. So, I strongly recommend you first try and solve some related problems. Coding Ninjas Studio

Please have a look at the algorithm, and then again, you must give it a try.




procedure minRequiredRange(vector<pair<int, int> > ranges, int N):


1.   L = INT_MAX, R = INT_MIN

2.   Begin loop from 0 to N:

3.    L = min(L, ranges[i].second).

4.    R = max(R, ranges[i].first)

5.   End loop

6.   if (R < L): return L and L

7.   Else: return L and R.

end procedure


Implementation in C++

// Find smallest range containing at least a single element from given N ranges
#include <bits/stdc++.h>
using namespace std;

// Function to find minimum range or domain 
void minRequiredRange(vector<pair<int, int>> ranges, int N)
   	// variable to store the starting of the range
    int L = INT_MAX;
   	// variable to store the ending of the range
    int R = INT_MIN;
   	// Loop to iterate over all N ranges given in problem statement
    for (int i = 0; i < N; i++)
       	// Calculate the smallest end point over all the given ranges
        L = min(L, ranges[i].second);

       	// Calcuate the largest starting point over all the given ranges
        R = max(R, ranges[i].first);
   	// If starting point is greater that the end point
    if (R < L)
       	// Print any integer between L and R
        cout << L << " " << L;
       	// Print Answer
        cout << L << " " << R;
int main()
    vector<pair<int, int>> ranges
        { 1, 4 },
        { 4, 5 },
        { 7, 9 },
        { 9, 12 }
    minRequiredRange(ranges, ranges.size());
    return 0;



4 9

Complexity Analysis

Time Complexity: O(n).

Analysing Time Complexity:

Since the array is traversed only once.

Space complexity: O(1) since no extra variable is used.

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

Frequently Asked Questions

  1. What is the greedy approach?
    Answer) As the name suggests, being greedy means finding the closest solution possible. Decisions are made from the answer domain. It finds the best solution possible at each step.
  2. What is the minimisation problem?
    Answer) Finding minimum possible value for the given function.
  3. Which is vector and pair in C++?
    Answer) Vector refers to a dynamic array, and pair refers to a container containing two data elements simultaneously.

Key Takeaways

This article taught us how to Find the smallest range containing at least 1 element from given N ranges. We discussed its implementation using illustrations, pseudocode, and then proper code.

We hope you could take away critical techniques like analysing problems by walking over the execution of the examples and finding out the pattern followed in most problems.

Now, we recommend you practice problem sets based on binary search trees to master your fundamentals. You can get a wide range of questions similar to this on Coding Ninjas Studio

It's not the end. Must solve the problem of similar types. 

Happy Coding.

Previous article
Count Strings that Do Not Contain Any Alphabet’s Both Uppercase and Lowercase
Next article
Find a minimum number of bins to place N items(using the best-fit algorithm)
Live masterclass