Skip to main content
Talentd

Minimum Interval to Include Each Query - Solution & Explanation

HardArrayBinary SearchLine SweepSorting17 min readAsked at: Amazon, Google, Bloomberg
Practice this problem

Problem Statement

You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the ith interval starting at lefti and ending at righti (inclusive). The size of an interval is defined as the number of integers it contains, or more formally righti - lefti + 1.

You are also given an integer array queries. The answer to the jth query is the size of the smallest interval i such that lefti <= queries[j] <= righti. If no such interval exists, the answer is -1.

Return an array containing the answers to the queries.

 

Example 1:

Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3.
- Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3.
- Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1.
- Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.

Example 2:

Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output: [2,-1,4,6]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2.
- Query = 19: None of the intervals contain 19. The answer is -1.
- Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4.
- Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.

 

Constraints:

  • 1 <= intervals.length <= 105
  • 1 <= queries.length <= 105
  • intervals[i].length == 2
  • 1 <= lefti <= righti <= 107
  • 1 <= queries[j] <= 107

Approach Overview

Problem Overview: You get a list of intervals [start, end] and a list of query values. For each query, return the length of the smallest interval that contains that value. If no interval covers the query, return -1. The challenge is answering many queries efficiently without scanning every interval each time.

Approach 1: Sorting with Two Pointers Approach (O((n + q) log n) time, O(n) space)

Sort intervals by start time and sort queries while keeping their original indices. Use two pointers to iterate through intervals as queries increase. When the interval start becomes <= current query, add that interval to a structure tracking candidate intervals. Remove intervals whose end is smaller than the query. The smallest valid interval length is tracked dynamically. This approach relies heavily on sorting and pointer movement across both arrays.

Approach 2: Binary Search with Interval Indexing (O((n + q) log n) time, O(n) space)

Sort intervals by start value and build indexed structures for fast lookups. For each query, use binary search to locate the first interval whose start could contain the query. From that position, evaluate candidate intervals that still satisfy start ≤ query ≤ end. Track the minimum interval length while scanning valid ranges. Binary search reduces the search window for each query instead of checking all intervals.

Approach 3: Priority Queue with Sorting (O((n + q) log n) time, O(n) space)

Sort intervals by start and queries by value. As you process each query from smallest to largest, push intervals whose start ≤ query into a min heap keyed by interval length. Remove heap entries where end < query because they no longer cover the query. The top of the heap always gives the smallest interval that currently contains the query. This combination of priority queue, sorting, and a sweep over queries behaves like a classic line sweep technique.

Approach 4: Sorting and Binary Search (O((n + q) log n) time, O(n) space)

Sort intervals and preprocess useful metadata such as interval lengths and endpoints. For each query, use binary search to locate candidate intervals and evaluate which ones cover the query. Maintain the smallest length among valid matches. This method is straightforward to implement when binary search utilities are readily available and avoids maintaining a dynamic heap.

Recommended for interviews: The priority queue with sorting approach is the one most interviewers expect. It demonstrates control of offline query processing, heap operations, and efficient interval filtering. Showing the brute-force idea first (checking every interval per query) proves you understand the problem, but moving to the heap-based sweep with O((n + q) log n) complexity shows strong algorithmic thinking.

Approach 1: Sorting with Two Pointers Approach

Sort both intervals by size and queries by their values. Use a two-pointer technique to iterate over intervals and queries simultaneously, maintaining a data structure (min-heap) to efficiently access the interval with the smallest size that contains the current query. This allows you to efficiently process each query in O(log n) time on average, leading to a total time complexity of O((m + n) log n), where m is the number of queries and n is the number of intervals.

In this Python implementation, intervals are first sorted by their size, then by their start point. Queries are sorted to process from left to right. A min-heap is used to keep the smallest interval available that includes the query. We iteratively check each query against available intervals and update the heap if an interval does not satisfy the query condition anymore.

Code

Python

Python

Complexity

Time Complexity: O((n + m) log n), where n is the number of intervals and m is the number of queries. Space Complexity: O(n), used by the heap.

Try this approach in the editor →

Approach 2: Binary Search with Interval Indexing

Sort intervals and queries. For each query, use binary search to find the smallest interval containing it. You maintain an active set of intervals and perform binary search over this set for each query. This approach efficiently handles comparisons and updates to determine the smallest intervals.

This Javascript solution sorts intervals by size as primary criteria. For each query, intervals are maintained in a min-heap that helps track the smallest interval containing the current query. Intervals are added or removed from this heap through a loop, ensuring complexity remains reasonable.

Code

JavaScript

JavaScript

Complexity

Time Complexity: O((n + m) log n), due to both sorting intervals and reorganizing the heap. Space Complexity: O(n), for the data structures used.

Try this approach in the editor →

Approach 3: Priority Queue with Sorting

Approach Description: We first sort the intervals based on their start points and prepare a priority queue (or heap) to process them by size. For each query, process the intervals that start before or when the query appears and use the priority queue to find the smallest valid interval.

This Python code utilizes a priority queue (min-heap) to find the smallest interval for every query. We sort the intervals and process each query in sorted order, adding all potential intervals into the heap and discarding irrelevant ones. The heap ensures that we can quickly retrieve the smallest interval size that contains the query.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O((n + m) log n), where n is the number of intervals and m is the number of queries. We sort intervals and queries, and maintain a heap for processing.

Space Complexity: O(n) for the heap that stores intervals.

Try this approach in the editor →

Approach 4: Sorting and Binary Search

Approach Description: Sort the intervals by their starting and ending points. For each query, use binary search to find the smallest interval that contains the query point in this sorted list. Keeping track of active intervals helps efficiently locate the correct interval size.

This C++ code makes use of sorting and a map to emulate a priority queue for managing interval ranges. Intervals are sorted, and for each query, relevant intervals are checked using a combination of sorting and direct access through map operations.

Code

C++JavaScript

C++

JavaScript

Complexity

Time Complexity: O(n log n + m log n) due to sorting and potential binary search operations.

Space Complexity: O(n) for the map to keep track of interval sizes.

Try this approach in the editor →

Approach 5: Sorting + Offline Query + Priority Queue (Min Heap)

We notice that the order of queries does not affect the answer, and the intervals involved do not change. Therefore, we consider sorting all queries in ascending order, and sorting all intervals in ascending order of the left endpoint.

We use a priority queue (min heap) pq to maintain all current intervals. Each element in the queue is a pair (v, r), representing an interval with length v and right endpoint r. Initially, the priority queue is empty. In addition, we define a pointer i that points to the current interval being traversed, and initially i=0.

We traverse each query (x, j) in ascending order and perform the following operations:

  • If the pointer i has not traversed all intervals, and the left endpoint of the current interval [a, b] is less than or equal to x, then we add this interval to the priority queue and move the pointer i one step forward. Repeat this process.
  • If the priority queue is not empty, and the right endpoint of the heap top element is less than x, then we pop the heap top element. Repeat this process.
  • At this point, if the priority queue is not empty, then the heap top element is the smallest interval containing x. We add its length v to the answer array ans.

After the above process is over, we return the answer array ans.

The time complexity is O(n times log n + m times log m), and the space complexity is O(n + m). Where n and m are the lengths of the arrays intervals and queries respectively.

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
Sorting with Two Pointers Approach

Time Complexity: O((n + m) log n), where n is the number of intervals and m is the number of queries. Space Complexity: O(n), used by the heap.

Binary Search with Interval Indexing

Time Complexity: O((n + m) log n), due to both sorting intervals and reorganizing the heap. Space Complexity: O(n), for the data structures used.

Priority Queue with Sorting

Time Complexity: O((n + m) log n), where n is the number of intervals and m is the number of queries. We sort intervals and queries, and maintain a heap for processing.

Space Complexity: O(n) for the heap that stores intervals.

Sorting and Binary Search

Time Complexity: O(n log n + m log n) due to sorting and potential binary search operations.

Space Complexity: O(n) for the map to keep track of interval sizes.

Sorting + Offline Query + Priority Queue (Min Heap)—

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sorting with Two PointersO((n + q) log n)O(n)When processing queries offline with sorted intervals
Binary Search with Interval IndexingO((n + q) log n)O(n)When you want direct lookup of candidate intervals using binary search
Priority Queue with SortingO((n + q) log n)O(n)Best general solution; dynamically tracks smallest valid interval
Sorting and Binary SearchO((n + q) log n)O(n)When intervals are preprocessed and heap usage is unnecessary

Video Solution

Minimum Interval to Include Each Query - Leetcode 1851 - Python • NeetCode • 68,395 views views

Watch 9 more video solutions →

Frequently Asked Questions

Is Minimum Interval to Include Each Query easy or hard?
Minimum Interval to Include Each Query is classified as a Hard problem. The difficulty comes from combining sorting, offline query processing, and heap maintenance while ensuring each interval is processed only once to achieve O((n + q) log n) performance.
Minimum Interval to Include Each Query Python or Java solution?
Python implementations typically use the heapq module to maintain the min heap of candidate intervals, while Java solutions use PriorityQueue. Both follow the same pattern: sort intervals, sort queries with indices, push valid intervals into the heap, remove expired intervals, and record the smallest interval length.
What is the best approach for Minimum Interval to Include Each Query?
The most effective solution sorts intervals and queries, then uses a min heap to track candidate intervals. As queries increase, intervals whose start is ≤ query are pushed into the heap, and intervals that end before the query are removed. The smallest interval length in the heap is the answer for that query. This priority queue approach runs in O((n + q) log n) time.
How to solve Minimum Interval to Include Each Query in O((n+q) log n)?
Sort intervals by start and queries by value. Iterate through queries in increasing order while inserting intervals whose start ≤ query into a min heap keyed by interval length. Remove intervals whose end < query because they no longer cover the query. The heap top gives the smallest valid interval length for that query.
Is Minimum Interval to Include Each Query asked at Google/Amazon/Meta?
Interval processing and heap-based query problems frequently appear in interviews at companies like Google, Amazon, and Meta. The problem tests understanding of sorting, line sweep techniques, and priority queue optimization, which are common patterns in real interview questions.
What data structure is used in Minimum Interval to Include Each Query?
The core data structure is a min heap (priority queue) that stores intervals currently capable of covering the query. Each heap element is typically ordered by interval length so the smallest covering interval can be retrieved in O(log n) time. Sorting and binary search are also used for efficient traversal.
What is the time complexity of Minimum Interval to Include Each Query?
The optimal algorithm runs in O((n + q) log n) time where n is the number of intervals and q is the number of queries. Sorting intervals and queries takes O(n log n + q log q), and each interval is pushed and popped from the heap at most once. Space complexity is O(n) for the heap and query indexing.

Ready to solve this problem?

Practice Minimum Interval to Include Each Query with our built-in code editor and test cases.

Practice on FleetCode
Previous

Number of Flowers in Full Bloom