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 <= 1051 <= queries.length <= 105intervals[i].length == 21 <= lefti <= righti <= 1071 <= queries[j] <= 107Problem 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.
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.
Python
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.
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.
JavaScript
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.
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.
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.
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.
C++
JavaScript
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.
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:
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.x, then we pop the heap top element. Repeat this process.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.
| Approach | Complexity |
|---|---|
| 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: Space Complexity: |
| Sorting and Binary Search | Time Complexity: Space Complexity: |
| Sorting + Offline Query + Priority Queue (Min Heap) | — |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sorting with Two Pointers | O((n + q) log n) | O(n) | When processing queries offline with sorted intervals |
| Binary Search with Interval Indexing | O((n + q) log n) | O(n) | When you want direct lookup of candidate intervals using binary search |
| Priority Queue with Sorting | O((n + q) log n) | O(n) | Best general solution; dynamically tracks smallest valid interval |
| Sorting and Binary Search | O((n + q) log n) | O(n) | When intervals are preprocessed and heap usage is unnecessary |
Minimum Interval to Include Each Query - Leetcode 1851 - Python • NeetCode • 63,310 views views
Watch 9 more video solutions →Practice Minimum Interval to Include Each Query with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor