Difficulty: 🔴 Hard
Topics: Array, Binary Search, Sweep Line, Sorting, Heap (Priority Queue)

Solution

Problem Understanding

The problem gives us a collection of inclusive integer intervals and a list of query values. For every query, we must determine the size of the smallest interval that contains that query value.

An interval [left, right] contains a query q if:

left <= q <= right

The size of an interval is:

right - left + 1

For each query, we are not looking for just any interval that contains it. We specifically need the interval with the minimum size among all valid intervals.

For example, if the intervals are:

[1, 10]
[3, 5]
[4, 4]

and the query is 4, then all three intervals contain 4, but their sizes are:

10
3
1

So the answer is 1, because [4,4] is the smallest valid interval.

The input sizes are large:

Up to 10^5 intervals
Up to 10^5 queries

A naive solution that checks every interval for every query would require:

10^5 * 10^5 = 10^10

operations in the worst case, which is far too slow.

The constraints strongly suggest that we need an algorithm close to:

O(n log n)

O((n + q) log n)

where:

n = len(intervals)
q = len(queries)

Several important edge cases appear immediately:

Queries that are not inside any interval should return -1
Multiple intervals may contain the same query
Intervals may overlap heavily
Queries may appear in arbitrary order
Multiple queries can have the same value
Intervals can have size 1, such as [4,4]
A very large interval may contain many queries, but a smaller interval might still be the correct answer

The problem guarantees:

Every interval is valid because lefti <= righti
All values are positive integers
Input arrays are non-empty This problem asks us to answer multiple range queries efficiently over a set of intervals. Each interval is defined by a starting point and an ending point, and its size is simply the number of integers it covers, computed as right - left + 1.

For every query value, we need to find all intervals that contain this query point, meaning the interval’s start is less than or equal to the query and its end is greater than or equal to the query. Among all such valid intervals, we must return the smallest interval size. If no interval contains the query point, we return -1.

The key challenge is that both the number of intervals and the number of queries can be up to 100,000, so any solution that checks every interval for every query would be too slow.

The input guarantees that interval boundaries and queries are positive integers up to 10^7, and intervals are inclusive. Important edge cases include queries that fall outside all intervals, multiple overlapping intervals with different sizes, and intervals that collapse to a single point.

A naive approach would repeatedly scan all intervals for each query, but this is infeasible at scale. The structure suggests we need to preprocess intervals and answer queries in near-logarithmic time.

Approaches

Brute Force Approach

The most direct solution is to process each query independently.

For every query:

Iterate through all intervals
Check whether the interval contains the query
If it does, compute its size
Track the minimum size seen so far
If no interval contains the query, return -1

This approach is straightforward and obviously correct because it explicitly checks every possible interval that could contribute to the answer.

However, its performance is unacceptable.

If there are:

n intervals
q queries

then the total complexity becomes:

O(n * q)

With both values up to 10^5, this becomes too slow.

Optimal Approach

The key observation is that queries can be processed in sorted order.

Suppose we sort:

intervals by starting point
queries by value

Then, as we move from smaller queries to larger queries, we can incrementally maintain the set of intervals that could possibly contain the current query.

We use a min-heap to efficiently retrieve the smallest interval among all currently valid intervals.

For every query:

Add all intervals whose left <= query
Remove intervals whose right < query
The remaining intervals are exactly the intervals that contain the query
The heap top gives the smallest interval size immediately

This transforms the problem into a sweep line algorithm with a priority queue.

Approach Comparison

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n * q)	O(1)	Checks every interval for every query
Optimal	O((n + q) log n)	O(n)	Uses sorting, sweep line, and min-heap

Algorithm Walkthrough

Step 1: Sort the intervals by starting position

We first sort intervals by their left endpoint.

This allows us to process intervals incrementally as queries increase.

For example:

intervals = [[3,6],[1,4],[2,4]]

becomes:

[[1,4],[2,4],[3,6]]

Step 2: Pair queries with their original indices

We must return answers in the original query order.

After sorting queries, their positions would otherwise be lost.

So we create pairs:

(query_value, original_index)

Example:

queries = [2,3,4,5]

becomes:

[(2,0),(3,1),(4,2),(5,3)]

Then we sort these pairs by query value.

Step 3: Create a min-heap

The heap stores candidate intervals.

Each heap entry contains:

(interval_size, interval_right)

Why these values?

interval_size allows the heap to prioritize the smallest interval
interval_right allows us to determine whether the interval still contains the current query

Step 4: Sweep through queries in sorted order

We maintain a pointer into the sorted intervals array.

For each query:

4.1 Add newly eligible intervals

While:

interval.left <= query

we push the interval into the heap.

The interval size is:

right - left + 1

At this point, the heap contains intervals that have started before or at the query.

Step 5: Remove expired intervals

Some intervals no longer contain the current query.

If:

interval.right < query

then the interval cannot contain this query or any future query.

So we remove it from the heap.

Step 6: Determine the answer

After cleanup:

Every interval remaining in the heap contains the query
The heap top is the smallest such interval

If the heap is empty:

answer = -1

Otherwise:

answer = heap[0].size

Step 7: Store the answer in the original position

Because queries were sorted, we store the result using the original query index.

This restores the final answer order correctly.

Why it works

The algorithm maintains an important invariant:

Before answering a query, the heap contains exactly the intervals that contain that query.

This is guaranteed because:

We add every interval whose left endpoint is small enough
We remove every interval whose right endpoint is too small

Therefore, the heap always represents the valid candidate intervals for the current query.

Since the heap is ordered by interval size, the smallest valid interval is always at the top. The brute-force method iterates over every query and, for each query, scans all intervals to check whether the interval contains the query. If it does, we compute its size and track the minimum.

This approach is correct because it directly applies the problem definition without optimization. However, it is far too slow because it performs O(n) work per query, leading to O(n × q), which is up to 10^10 operations.

Key Insight

The critical observation is that we want to efficiently answer: “Among all intervals covering a point, what is the minimum length?”

If we process queries in sorted order, we can also process intervals in sorted order of their start points. For each query, we maintain a set of “active intervals”, meaning intervals whose left endpoint is already ≤ query. Among these active intervals, we only want those whose right endpoint is still ≥ query.

To efficiently retrieve the smallest interval among active ones, we use a min-heap ordered by interval size. However, we also need to lazily discard intervals that no longer cover the query (their right endpoint is too small).

This leads to a sweep line approach combined with a priority queue.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(n × q)	O(1)	Check all intervals per query
Optimal (Sweep Line + Heap)	O((n + q) log n)	O(n)	Sort intervals and queries, use min-heap

Algorithm Walkthrough

First, we sort all intervals by their left endpoint. This ensures that as we move through queries in increasing order, we can progressively add intervals that become “active”.
We transform queries into a list of pairs (query_value, original_index) and sort them by query value. This allows us to process queries in ascending order while still being able to restore original ordering.
We initialize a min-heap that will store active intervals. Each heap entry contains (interval_size, right_endpoint) so we can always retrieve the smallest interval efficiently.
We maintain a pointer over the sorted intervals. For each query, we add all intervals whose left endpoint is less than or equal to the query into the heap. These intervals are now candidates because they start before or at the query.
After adding intervals, we remove invalid intervals from the heap. Specifically, while the heap top has a right endpoint less than the current query, it cannot cover the query anymore, so we discard it.
If the heap is not empty after cleanup, the top element gives the smallest valid interval covering the query. Otherwise, we assign -1.
We continue this process for all queries in sorted order.

The key idea is that each interval is pushed into the heap exactly once and popped at most once, ensuring efficiency.

Why it works

The algorithm maintains the invariant that at each query, the heap contains exactly those intervals whose left endpoint is ≤ query and have not yet expired (right endpoint ≥ query). Since the heap is ordered by interval size, the top always represents the smallest valid interval, guaranteeing correctness.

Python Solution

from typing import List
import heapq

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        intervals.sort()

        sorted_queries = sorted(
            (query, index)
            for index, query in enumerate(queries)
        )

        answers = [-1] * len(queries)

        min_heap = []

        interval_index = 0
        total_intervals = len(intervals)

        for query_value, query_index in sorted_queries:

            while (
                interval_index < total_intervals
                and intervals[interval_index][0] <= query_value
            ):
                left, right = intervals[interval_index]

                interval_size = right - left + 1

                heapq.heappush(
                    min_heap,
                    (interval_size, right)
                )

                interval_index += 1

            while min_heap and min_heap[0][1] < query_value:
                heapq.heappop(min_heap)

            if min_heap:
                answers[query_index] = min_heap[0][0]

        return answers

The implementation begins by sorting intervals according to their starting points. This supports the sweep line strategy because intervals become eligible in sorted order as queries increase.

The queries are paired with their original indices before sorting. This is necessary because the algorithm processes queries in ascending order, but the final result must match the original query ordering.

The heap stores tuples of:

(interval_size, interval_right)

Python's heapq implements a min-heap, so the interval with the smallest size automatically appears at the top.

For each query, the first loop inserts all intervals whose left endpoint is less than or equal to the query. These intervals could potentially contain the query.

The second loop removes intervals whose right endpoint is smaller than the query. Such intervals are expired because they no longer overlap the current sweep position.

After these updates, the heap contains only valid candidate intervals. The smallest interval size is therefore available at min_heap[0][0].

The answer is stored using the original query index so that the final output order matches the input order.

    sorted_queries = sorted([(q, i) for i, q in enumerate(queries)])
    result = [-1] * len(queries)
    
    min_heap = []
    i = 0
    
    for q, qi in sorted_queries:
        while i < len(intervals) and intervals[i][0] <= q:
            left, right = intervals[i]
            size = right - left + 1
            heapq.heappush(min_heap, (size, right))
            i += 1
        
        while min_heap and min_heap[0][1] < q:
            heapq.heappop(min_heap)
        
        if min_heap:
            result[qi] = min_heap[0][0]
        else:
            result[qi] = -1
    
    return result


### Code Explanation

The code first sorts intervals so we can process them in increasing order of start time. Then it sorts queries while keeping track of original indices.

The heap stores candidate intervals as `(size, right)`. As we move through queries, we push all intervals whose start is valid. Then we remove intervals that no longer cover the query.

Finally, the smallest interval size is taken from the heap top.

This matches the sweep line logic described earlier, ensuring each interval is processed efficiently.

## Go Solution

```go
package main

import (
	"container/heap"
	"sort"
)

type HeapItem struct {
	size  int
	right int
}

type MinHeap []HeapItem

func (h MinHeap) Len() int {
	return len(h)
}

func (h MinHeap) Less(i, j int) bool {
	return h[i].size < h[j].size
}

func (h MinHeap) Swap(i, j int) {
	h[i], h[j] = h[j], h[i]
}

func (h *MinHeap) Push(x interface{}) {
	*h = append(*h, x.(HeapItem))
}

func (h *MinHeap) Pop() interface{} {
	old := *h
	n := len(old)

	item := old[n-1]

	*h = old[:n-1]

	return item
}

func minInterval(intervals [][]int, queries []int) []int {
	sort.Slice(intervals, func(i, j int) bool {
		return intervals[i][0] < intervals[j][0]
	})

	type Query struct {
		value int
		index int
	}

	sortedQueries := make([]Query, len(queries))

	for i, q := range queries {
		sortedQueries[i] = Query{
			value: q,
			index: i,
		}
	}

	sort.Slice(sortedQueries, func(i, j int) bool {
		return sortedQueries[i].value < sortedQueries[j].value
	})

	answers := make([]int, len(queries))

	for i := range answers {
		answers[i] = -1
	}

	minHeap := &MinHeap{}
	heap.Init(minHeap)

	intervalIndex := 0

	for _, query := range sortedQueries {

		for intervalIndex < len(intervals) &&
			intervals[intervalIndex][0] <= query.value {

			left := intervals[intervalIndex][0]
			right := intervals[intervalIndex][1]

			size := right - left + 1

			heap.Push(minHeap, HeapItem{
				size:  size,
				right: right,
			})

			intervalIndex++
		}

		for minHeap.Len() > 0 &&
			(*minHeap)[0].right < query.value {

			heap.Pop(minHeap)
		}

		if minHeap.Len() > 0 {
			answers[query.index] = (*minHeap)[0].size
		}
	}

	return answers
}

The Go implementation follows the same algorithmic structure as the Python version, but Go requires an explicit heap implementation using the container/heap package.

A custom MinHeap type is created with the required interface methods:

Len
Less
Swap
Push
Pop

The heap stores HeapItem structs containing:

size
right

Go slices are dynamically sized, so they naturally support heap operations. The implementation initializes all answers to -1 because some queries may not be covered by any interval.

Integer overflow is not an issue because interval sizes are at most:

10^7

which easily fits inside Go's int type. "sort" )

type Interval struct { left, right int }

type Item struct { size int right int }

type MinHeap []Item

func (h MinHeap) Len() int { return len(h) } func (h MinHeap) Less(i, j int) bool { return h[i].size < h[j].size } func (h MinHeap) Swap(i, j int) { h[i], h[j] = h[j], h[i] }

func (h *MinHeap) Push(x interface{}) { *h = append(*h, x.(Item)) }

func (h *MinHeap) Pop() interface{} { old := *h n := len(old) x := old[n-1] *h = old[:n-1] return x }

func minInterval(intervals [][]int, queries []int) []int { type Q struct { val int idx int }

sort.Slice(intervals, func(i, j int) bool {
    return intervals[i][0] < intervals[j][0]
})

qs := make([]Q, len(queries))
for i, q := range queries {
    qs[i] = Q{q, i}
}

sort.Slice(qs, func(i, j int) bool {
    return qs[i].val < qs[j].val
})

h := &MinHeap{}
res := make([]int, len(queries))
for i := range res {
    res[i] = -1
}

idx := 0

for _, q := range qs {
    for idx < len(intervals) && intervals[idx][0] <= q.val {
        left := intervals[idx][0]
        right := intervals[idx][1]
        size := right - left + 1
        heap.Push(h, Item{size, right})
        idx++
    }

    for h.Len() > 0 {
        top := (*h)[0]
        if top.right < q.val {
            heap.Pop(h)
        } else {
            break
        }
    }

    if h.Len() > 0 {
        res[q.idx] = (*h)[0].size
    }
}

return res

}


### Go-specific notes

Go requires explicit heap implementation via `container/heap` style interfaces, although here we manually implemented a minimal heap structure. We also define structs for clarity. Unlike Python, we must manage type assertions and struct-based comparisons explicitly.

## Worked Examples

### Example 1

Input:

intervals = [[1,4],[2,4],[3,6],[4,4]] queries = [2,3,4,5]


### Step 1: Sort intervals

[[1,4],[2,4],[3,6],[4,4]]


Already sorted.

### Step 2: Sort queries with indices

[(2,0),(3,1),(4,2),(5,3)]


### Processing Query = 2

Add intervals with `left <= 2`:

| Interval | Size | Heap |
| --- | --- | --- |
| [1,4] | 4 | [(4,4)] |
| [2,4] | 3 | [(3,4),(4,4)] |

Remove expired intervals:

None.

Heap top:

(3,4)


Answer:


### Processing Query = 3

Add intervals with `left <= 3`:

| Interval | Size |
| --- | --- |
| [3,6] | 4 |

Heap becomes:

[(3,4),(4,4),(4,6)]


Remove expired intervals:

None.

Answer:


### Processing Query = 4

Add intervals with `left <= 4`:

| Interval | Size |
| --- | --- |
| [4,4] | 1 |

Heap becomes:

[(1,4),(3,4),(4,6),(4,4)]


Remove expired intervals:

None.

Answer:


### Processing Query = 5

No new intervals added.

Remove expired intervals:

(1,4) (3,4) (4,4)


Remaining heap:

[(4,6)]


Answer:


Final output:

[3,3,1,4]


### Example 2

Input:

intervals = [[2,3],[2,5],[1,8],[20,25]] queries = [2,19,5,22]


### Sorted intervals

[[1,8],[2,3],[2,5],[20,25]]


### Sorted queries

[(2,0),(5,2),(19,1),(22,3)]


### Processing Query = 2

Add:

[1,8] size=8 [2,3] size=2 [2,5] size=4


Heap top:


Answer:


### Processing Query = 5

Remove expired interval:

[2,3]


Remaining valid intervals:

[2,5] [1,8]


Smallest size:


### Processing Query = 19

All intervals expire.

Heap becomes empty.

Answer:

-1


### Processing Query = 22

Add:

[20,25]


Size:


Answer:


Final output:

[2,-1,4,6]

Intervals: `[[1,4],[2,4],[3,6],[4,4]]`

Queries: `[2,3,4,5]`

Sorted queries: `(2,0), (3,1), (4,2), (5,3)`

At query = 2:

- Add intervals starting ≤ 2: `[1,4], [2,4]`
- Heap: (4,4), (3,4)
- Min is 3

At query = 3:

- Add `[3,6]`
- Heap: (4,4), (3,4), (4,6)
- Min is still 3

At query = 4:

- Add `[4,4]`
- Heap includes (1,4)
- Min becomes 1

At query = 5:

- Remove expired intervals (those ending < 5)
- Only `[3,6]` remains
- Answer = 4

Final output: `[3,3,1,4]`

### Example 2

Intervals: `[[2,3],[2,5],[1,8],[20,25]]`

Queries: `[2,19,5,22]`

At query = 2:

- Active intervals: all starting ≤ 2
- Valid: `[2,3], [2,5], [1,8]`
- Min size = 2

At query = 19:

- Only `[1,8]` and `[20,25]` considered, but neither fully contains 19
- Heap becomes empty
- Answer = -1

At query = 5:

- Valid: `[2,5], [1,8]`
- Min size = 4

At query = 22:

- Valid: `[20,25]`
- Size = 6

Final output: `[2,-1,4,6]`

## Complexity Analysis

| Measure | Complexity | Explanation |
| --- | --- | --- |
| Time | O((n + q) log n) | Sorting plus heap insertions/removals |
| Space | O(n) | Heap storage and auxiliary arrays |

The intervals are sorted once, costing:

O(n log n)


The queries are also sorted:

O(q log q)


Each interval is inserted into the heap exactly once and removed exactly once. Heap operations cost:

O(log n)


Therefore the total heap cost is:

O(n log n)


Combining all costs gives:

O((n + q) log n)


The heap can contain up to `n` intervals simultaneously, so the space complexity is `O(n)`.

## Test Cases

```python
from typing import List

class Solution:
    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
        import heapq

        intervals.sort()

        sorted_queries = sorted(
            (q, i) for i, q in enumerate(queries)
        )

        result = [-1] * len(queries)

        heap = []

        i = 0

        for query, original_index in sorted_queries:

            while i < len(intervals) and intervals[i][0] <= query:
                left, right = intervals[i]

                heapq.heappush(
                    heap,
                    (right - left + 1, right)
                )

                i += 1

            while heap and heap[0][1] < query:
                heapq.heappop(heap)

            if heap:
                result[original_index] = heap[0][0]

        return result

solution = Solution()

assert solution.minInterval(
    [[1,4],[2,4],[3,6],[4,4]],
    [2,3,4,5]
) == [3,3,1,4]  # provided example 1

assert solution.minInterval(
    [[2,3],[2,5],[1,8],[20,25]],
    [2,19,5,22]
) == [2,-1,4,6]  # provided example 2

assert solution.minInterval(
    [[1,1]],
    [1]
) == [1]  # single interval and single query

assert solution.minInterval(
    [[1,2]],
    [3]
) == [-1]  # query outside all intervals

assert solution.minInterval(
    [[1,10],[2,3],[4,5]],
    [2,4]
) == [2,2]  # smaller intervals beat larger interval

assert solution.minInterval(
    [[5,5],[1,100]],
    [5]
) == [1]  # exact single-point interval

assert solution.minInterval(
    [[1,4],[1,4],[1,4]],
    [2]
) == [4]  # duplicate intervals

assert solution.minInterval(
    [[1,2],[3,4],[5,6]],
    [1,3,5,7]
) == [2,2,2,-1]  # mixture of valid and invalid queries

assert solution.minInterval(
    [[1,10000000]],
    [1,5000000,10000000]
) == [10000000,10000000,10000000]  # maximum interval size

assert solution.minInterval(
    [[2,4],[3,7],[1,10]],
    [2,3,4,5,6]
) == [3,3,3,5,5]  # overlapping intervals
| Time | O((n + q) log n) | Sorting plus each interval pushed and popped once |
| Space | O(n) | Heap stores active intervals |

The dominant cost comes from sorting intervals and queries, and from heap operations. Each interval enters and leaves the heap at most once, ensuring logarithmic overhead per operation.

## Test Cases

assert Solution().minInterval([[1,4],[2,4],[3,6],[4,4]], [2,3,4,5]) == [3,3,1,4] # example 1 assert Solution().minInterval([[2,3],[2,5],[1,8],[20,25]], [2,19,5,22]) == [2,-1,4,6] # example 2

single interval exact match

assert Solution().minInterval([[5,5]], [5]) == [1]

query outside all intervals

assert Solution().minInterval([[1,2],[3,4]], [10]) == [-1]

overlapping intervals same coverage

assert Solution().minInterval([[1,10],[2,9],[3,8]], [5]) == [6]

multiple queries with shared intervals

assert Solution().minInterval([[1,5],[2,6],[4,8]], [2,4,6]) == [5,5,5]


| Test | Why |
| --- | --- |
| Example 1 | Validates overlapping intervals and minimum selection |
| Example 2 | Validates uncovered queries returning `-1` |
| Single interval/query | Smallest possible valid input |
| Query outside interval | Ensures missing coverage handled correctly |
| Smaller interval preferred | Confirms heap chooses minimum size |
| Single-point interval | Tests interval size `1` |
| Duplicate intervals | Ensures duplicates do not break logic |
| Mixed valid/invalid queries | Tests repeated heap cleanup |
| Maximum interval size | Verifies large numeric ranges |
| Complex overlaps | Tests multiple active intervals simultaneously |

## Edge Cases

### Queries Not Covered by Any Interval

A common source of bugs occurs when no interval contains a query. Some implementations may accidentally leave stale intervals inside the heap or incorrectly return a previous answer.

For example:

intervals = [[1,2]] queries = [5]


The implementation handles this correctly by removing all expired intervals before answering the query. If the heap becomes empty, the answer remains `-1`.

### Single-Point Intervals

Intervals such as:

[4,4]


have size `1`.

These intervals are especially important because they are often the optimal answer. A buggy implementation might incorrectly compute the size as:

right - left


instead of:

right - left + 1


The implementation explicitly uses:

right - left + 1


which correctly handles inclusive intervals.

### Large Overlapping Intervals

Another tricky case occurs when many intervals overlap the same query.

Example:

intervals = [[1,100],[20,30],[25,26]] query = 25


All intervals contain `25`, but the smallest interval must be chosen.

The heap structure guarantees correctness because intervals are ordered by size, not by start or end position. Even if a large interval was added earlier, the smallest interval automatically rises to the top of the heap.
| example 1 | standard overlapping case |
| example 2 | mixed coverage and missing queries |
| single interval | minimal boundary correctness |
| no coverage | all queries return -1 |
| nested intervals | verifies smallest selection |
| multiple queries | ensures reuse of heap state |

## Edge Cases

One important edge case is when all intervals are identical or fully nested. In this scenario, many intervals remain active simultaneously, and the algorithm must correctly pick the smallest one rather than the most recent or largest.

Another edge case occurs when queries fall entirely outside the range of all intervals. The heap will remain empty throughout processing, and the implementation must correctly return `-1` without attempting invalid heap access.

A third edge case involves intervals that collapse into a single point, where `left == right`. These intervals have size 1, and the algorithm must ensure they are correctly prioritized when a query exactly matches that point, even if larger overlapping intervals also exist.

LeetCode 1851 - Minimum Interval to Include Each Query

Solution

Problem Understanding

Approaches

Brute Force Approach

Optimal Approach

Approach Comparison

Algorithm Walkthrough

Step 1: Sort the intervals by starting position

Step 2: Pair queries with their original indices

Step 3: Create a min-heap

Step 4: Sweep through queries in sorted order

4.1 Add newly eligible intervals

Step 5: Remove expired intervals

Step 6: Determine the answer

Step 7: Store the answer in the original position

Why it works

Key Insight

Algorithm Walkthrough

Why it works

Python Solution

single interval exact match

query outside all intervals

overlapping intervals same coverage

multiple queries with shared intervals