1851. Minimum Interval to Include Each Query (Hard)

Problem

You’re given intervals and queries. For each query q, find the length of the smallest interval that contains q (i.e., start ≤ q ≤ end), or -1 if no such interval exists.

Example

intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2, 3, 4, 5] → [3, 3, 1, 4]
intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2, 19, 5, 22] → [2, -1, 4, 4]

LeetCode 1851 · Link · Hard

Try it yourself

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Starter code: this editor begins with intentional TODOs. Fill the function, run the embedded tests, then compare your solution with the worked approaches below.

Click Run Go to execute. Runs via the Go Playground API.

Approach 1: Brute force, per query, scan all intervals

For each query, iterate intervals and track the smallest containing length.

def min_interval(intervals, queries):
    result = []
    for q in queries:                         # L1: q iterations
        best = float('inf')
        for s, e in intervals:                # L2: n iterations per query
            if s <= q <= e:
                best = min(best, e - s + 1)
        result.append(best if best != float('inf') else -1)
    return result

function minInterval(intervals: number[][], queries: number[]): number[] {
    const result: number[] = [];
    for (const q of queries) {                // L1: q iterations
        let best = Infinity;
        for (const [s, e] of intervals) {     // L2: n iterations per query
            if (s <= q && q <= e) best = Math.min(best, e - s + 1);
        }
        result.push(best === Infinity ? -1 : best);
    }
    return result;
}

func minInterval(intervals [][]int, queries []int) []int {
    result := make([]int, len(queries))
    for qi, q := range queries {              // L1: q iterations
        best := math.MaxInt64
        for _, iv := range intervals {        // L2: n iterations per query
            if iv[0] <= q && q <= iv[1] {
                length := iv[1] - iv[0] + 1
                if length < best { best = length }
            }
        }
        if best == math.MaxInt64 { result[qi] = -1 } else { result[qi] = best }
    }
    return result
}

final class Solution {
    func minInterval(_ intervals: [[Int]], _ queries: [Int]) -> [Int] {
        queries.map { query in
            intervals.reduce(Int.max) { best, interval in
                interval[0] <= query && query <= interval[1] ? min(best, interval[1] - interval[0] + 1) : best
            }
        }.map { $0 == Int.max ? -1 : $0 }
    }
}

Each query independently scans every interval. No state shared across queries.

Complexity

Time: $O(n · q)$ .
Space: $O(q)$ .

Acceptable only when both n and q are small.

Approach 2: Offline queries + min-heap (canonical)

Sort queries and intervals by start. Walk queries in order; for each query, push all intervals whose start ≤ query into a min-heap keyed by length. Then pop heap entries whose end < query (they don’t contain it). The heap top is the smallest containing interval.

import heapq

def min_interval(intervals, queries):
    intervals.sort(key=lambda x: x[0])                       # L1: O(n log n)
    sorted_queries = sorted(enumerate(queries), key=lambda p: p[1])  # L2: O(q log q)

    result = [0] * len(queries)                               # L3: O(q)
    heap = []   # (length, end)                               # L4: O(1)
    i = 0                                                     # L5: O(1)
    for orig_idx, q in sorted_queries:                        # L6: O(q) outer loop
        while i < len(intervals) and intervals[i][0] <= q:   # L7: O(1) per check
            s, e = intervals[i]
            heapq.heappush(heap, (e - s + 1, e))              # L8: O(log n) per push
            i += 1
        while heap and heap[0][1] < q:                        # L9: O(1) per check
            heapq.heappop(heap)                               # L10: O(log n) per pop
        result[orig_idx] = heap[0][0] if heap else -1         # L11: O(1)
    return result

type HeapEntry = [number, number]; // [length, end]

function heapPush(heap: HeapEntry[], entry: HeapEntry): void {
    heap.push(entry);
    let i = heap.length - 1;
    while (i > 0) {
        const parent = (i - 1) >> 1;
        if (heap[parent][0] <= heap[i][0]) break;
        [heap[parent], heap[i]] = [heap[i], heap[parent]];
        i = parent;
    }
}

function heapPop(heap: HeapEntry[]): HeapEntry {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
        heap[0] = last;
        let i = 0;
        while (true) {
            let smallest = i;
            const l = 2 * i + 1, r = 2 * i + 2;
            if (l < heap.length && heap[l][0] < heap[smallest][0]) smallest = l;
            if (r < heap.length && heap[r][0] < heap[smallest][0]) smallest = r;
            if (smallest === i) break;
            [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
            i = smallest;
        }
    }
    return top;
}

function minInterval(intervals: number[][], queries: number[]): number[] {
    intervals.sort((a, b) => a[0] - b[0]);                    // L1: O(n log n)
    const sortedQueries = queries.map((q, idx) => [q, idx] as [number, number])
        .sort((a, b) => a[0] - b[0]);                         // L2: O(q log q)

    const result = new Array(queries.length).fill(0);         // L3: O(q)
    const heap: HeapEntry[] = [];                             // L4: O(1)
    let i = 0;                                                // L5: O(1)

    for (const [q, origIdx] of sortedQueries) {              // L6: O(q) outer loop
        while (i < intervals.length && intervals[i][0] <= q) { // L7: O(1) per check
            const [s, e] = intervals[i];
            heapPush(heap, [e - s + 1, e]);                   // L8: O(log n) per push
            i++;
        }
        while (heap.length > 0 && heap[0][1] < q) heapPop(heap); // L9/L10: O(log n) per pop
        result[origIdx] = heap.length > 0 ? heap[0][0] : -1; // L11: O(1)
    }
    return result;
}

func minInterval(intervals [][]int, queries []int) []int {
    sort.Slice(intervals, func(i, j int) bool {
        return intervals[i][0] < intervals[j][0]  // L1: O(n log n)
    })
    type iq struct{ val, idx int }
    sortedQueries := make([]iq, len(queries))
    for i, q := range queries { sortedQueries[i] = iq{q, i} }
    sort.Slice(sortedQueries, func(i, j int) bool {
        return sortedQueries[i].val < sortedQueries[j].val  // L2: O(q log q)
    })

    result := make([]int, len(queries))            // L3: O(q)
    h := &MinHeap{}                                // L4: O(1)
    heap.Init(h)
    i := 0                                         // L5: O(1)

    for _, sq := range sortedQueries {             // L6: O(q) outer loop
        q := sq.val
        for i < len(intervals) && intervals[i][0] <= q {  // L7: O(1) per check
            s, e := intervals[i][0], intervals[i][1]
            heap.Push(h, entry{e - s + 1, e})     // L8: O(log n) per push
            i++
        }
        for h.Len() > 0 && (*h)[0].end < q { heap.Pop(h) }  // L9/L10: O(log n) per pop
        if h.Len() > 0 { result[sq.idx] = (*h)[0].length } else { result[sq.idx] = -1 }  // L11: O(1)
    }
    return result
}

private struct IntervalCandidate { let length: Int; let end: Int }
final class Solution {
    func minInterval(_ intervals: [[Int]], _ queries: [Int]) -> [Int] {
        let sortedIntervals = intervals.sorted { $0[0] < $1[0] }
        let sortedQueries = queries.enumerated().sorted { $0.element < $1.element }
        var result = Array(repeating: -1, count: queries.count)
        var heap = BinaryHeap<IntervalCandidate> { $0.length == $1.length ? $0.end < $1.end : $0.length < $1.length }
        var index = 0
        for (original, query) in sortedQueries {
            while index < sortedIntervals.count && sortedIntervals[index][0] <= query { let interval = sortedIntervals[index]; heap.insert(IntervalCandidate(length: interval[1] - interval[0] + 1, end: interval[1])); index += 1 }
            while let top = heap.peek, top.end < query { _ = heap.removeRoot() }
            if let top = heap.peek { result[original] = top.length }
        }
        return result
    }
}

Where the time goes, line by line

Variables: n = len(intervals), q = len(queries).

Line	Per-call cost	Times executed	Contribution
L1 (sort intervals)	$O(n log n)$	1	$O(n log n)$
L2 (sort queries)	$O(q log q)$	1	$O(q log q)$
L3 (init result)	$O(q)$	1	$O(q)$
L6 (outer loop)	$O(1)$	q	$O(q)$
L7, L8 (push intervals)	$O(log n)$	n total	$O(n log n)$ ← dominates with L10
L9, L10 (pop stale)	$O(log n)$	n total	$O(n log n)$ ← dominates
L11 (read top)	$O(1)$	q	$O(q)$

Each interval is pushed at most once (L8) and popped at most once (L10). The outer loop sees q queries. Combined: $O((n + q)$ log(n + q)).

Complexity

Time: $O((n + q)$ log(n + q)), driven by L1/L2 sorts and L8/L10 heap operations.
Space: $O(n + q)$ .

Why offline sorting helps

Processing queries out of order turns a “for each query, find the best interval” problem into a stream. Sorting queries by value + sorting intervals by start makes the two monotonic, so a single sweep can answer every query.

Try this approach:

Click Run Python to execute. First run downloads Python (~10 MB, cached after that).

Click Run TS to execute. First run downloads Babel (~400 KB, cached after that).

Click Run Go to execute. Runs via the Go Playground API.

Approach 3: Segment tree / merge sort tree

More code and more flexibility. Used in competitive programming for online variants. The shape: coordinate-compress the endpoints, then for each interval do a range-min update of its length over [start, end]. Each query is a point query for the minimum length covering that coordinate.

Python
Swift

def min_interval(intervals, queries):
    # Coordinate compression
    coords = sorted(set([s for s, _ in intervals]
                        + [e for _, e in intervals]
                        + list(queries)))
    coord_idx = {c: i for i, c in enumerate(coords)}
    n = len(coords)
    INF = float('inf')
    tree = [INF] * (4 * max(n, 1))

    def update(node, lo, hi, l, r, val):
        if r < lo or hi < l:
            return
        if l <= lo and hi <= r:
            tree[node] = min(tree[node], val)
            return
        mid = (lo + hi) // 2
        update(2*node, lo, mid, l, r, val)
        update(2*node+1, mid+1, hi, l, r, val)

    def query(node, lo, hi, idx):
        if lo == hi:
            return tree[node]
        mid = (lo + hi) // 2
        if idx <= mid:
            return min(tree[node], query(2*node, lo, mid, idx))
        return min(tree[node], query(2*node+1, mid+1, hi, idx))

    for s, e in intervals:
        update(1, 0, n - 1, coord_idx[s], coord_idx[e], e - s + 1)

    result = []
    for q in queries:
        ans = query(1, 0, n - 1, coord_idx[q])
        result.append(ans if ans != INF else -1)
    return result

private struct RangeMinTree {
    private var values: [Int]
    private let count: Int
    init(count: Int) { self.count = count; values = Array(repeating: Int.max, count: max(1, count * 4)) }
    mutating func update(_ left: Int, _ right: Int, _ value: Int) { update(1, 0, count - 1, left, right, value) }
    private mutating func update(_ node: Int, _ low: Int, _ high: Int, _ left: Int, _ right: Int, _ value: Int) {
        if right < low || high < left { return }
        if left <= low && high <= right { values[node] = min(values[node], value); return }
        let middle = (low + high) / 2
        update(node * 2, low, middle, left, right, value)
        update(node * 2 + 1, middle + 1, high, left, right, value)
    }
    func query(_ index: Int) -> Int { query(1, 0, count - 1, index, Int.max) }
    private func query(_ node: Int, _ low: Int, _ high: Int, _ index: Int, _ best: Int) -> Int {
        let next = min(best, values[node])
        if low == high { return next }
        let middle = (low + high) / 2
        return index <= middle ? query(node * 2, low, middle, index, next) : query(node * 2 + 1, middle + 1, high, index, next)
    }
}
final class Solution {
    func minInterval(_ intervals: [[Int]], _ queries: [Int]) -> [Int] {
        let coordinates = Array(Set(intervals.flatMap { $0 } + queries)).sorted()
        let positions = Dictionary(uniqueKeysWithValues: coordinates.enumerated().map { ($0.element, $0.offset) })
        var tree = RangeMinTree(count: coordinates.count)
        for interval in intervals { tree.update(positions[interval[0]]!, positions[interval[1]]!, interval[1] - interval[0] + 1) }
        return queries.map { let answer = tree.query(positions[$0]!); return answer == Int.max ? -1 : answer }
    }
}

Skip unless the interviewer asks for $O(log n)$ per query online.

Summary

Approach	Time	Space
Per-query scan	$O(n · q)$	$O(q)$
Offline + heap sweep	$O((n + q)$ log (n + q))	$O(n + q)$
Segment tree	$O((n + q)$ log n)	$O(n)$

Offline query processing is a broadly useful pattern whenever you have a batch of queries that can be answered by a single sorted sweep.

# Quick smoke tests, paste into a REPL or save as test_1851_minimum_interval.py and run.
# Uses the canonical implementation (Approach 2).
import heapq

def min_interval(intervals, queries):
    intervals.sort(key=lambda x: x[0])
    sorted_queries = sorted(enumerate(queries), key=lambda p: p[1])

    result = [0] * len(queries)
    heap = []   # (length, end)
    i = 0
    for orig_idx, q in sorted_queries:
        while i < len(intervals) and intervals[i][0] <= q:
            s, e = intervals[i]
            heapq.heappush(heap, (e - s + 1, e))
            i += 1
        while heap and heap[0][1] < q:
            heapq.heappop(heap)
        result[orig_idx] = heap[0][0] if heap else -1
    return result

def _run_tests():
    # Example 1 from problem statement
    assert min_interval([[1,4],[2,4],[3,6],[4,4]], [2,3,4,5]) == [3,3,1,4]
    # Example 2
    assert min_interval([[2,3],[2,5],[1,8],[20,25]], [2,19,5,22]) == [2,-1,4,6]
    # Query with no matching interval
    assert min_interval([[1,3]], [5]) == [-1]
    # Single interval, single query inside
    assert min_interval([[1,10]], [5]) == [10]
    # Multiple queries all answered by same smallest interval
    assert min_interval([[1,5],[2,3]], [2,3]) == [2,2]
    print("all tests pass")

if __name__ == "__main__":
    _run_tests()

type HeapEntry = [number, number];

function heapPush(heap: HeapEntry[], entry: HeapEntry): void {
    heap.push(entry);
    let i = heap.length - 1;
    while (i > 0) {
        const parent = (i - 1) >> 1;
        if (heap[parent][0] <= heap[i][0]) break;
        [heap[parent], heap[i]] = [heap[i], heap[parent]];
        i = parent;
    }
}

function heapPop(heap: HeapEntry[]): HeapEntry {
    const top = heap[0];
    const last = heap.pop()!;
    if (heap.length > 0) {
        heap[0] = last;
        let i = 0;
        while (true) {
            let smallest = i;
            const l = 2 * i + 1, r = 2 * i + 2;
            if (l < heap.length && heap[l][0] < heap[smallest][0]) smallest = l;
            if (r < heap.length && heap[r][0] < heap[smallest][0]) smallest = r;
            if (smallest === i) break;
            [heap[i], heap[smallest]] = [heap[smallest], heap[i]];
            i = smallest;
        }
    }
    return top;
}

function minInterval(intervals: number[][], queries: number[]): number[] {
    intervals.sort((a, b) => a[0] - b[0]);
    const sortedQueries = queries.map((q, idx) => [q, idx] as [number, number])
        .sort((a, b) => a[0] - b[0]);
    const result = new Array(queries.length).fill(0);
    const heap: HeapEntry[] = [];
    let i = 0;
    for (const [q, origIdx] of sortedQueries) {
        while (i < intervals.length && intervals[i][0] <= q) {
            const [s, e] = intervals[i];
            heapPush(heap, [e - s + 1, e]);
            i++;
        }
        while (heap.length > 0 && heap[0][1] < q) heapPop(heap);
        result[origIdx] = heap.length > 0 ? heap[0][0] : -1;
    }
    return result;
}

console.assert(JSON.stringify(minInterval([[1,4],[2,4],[3,6],[4,4]], [2,3,4,5])) === JSON.stringify([3,3,1,4]));
console.assert(JSON.stringify(minInterval([[2,3],[2,5],[1,8],[20,25]], [2,19,5,22])) === JSON.stringify([2,-1,4,6]));
console.assert(JSON.stringify(minInterval([[1,3]], [5])) === JSON.stringify([-1]));
console.assert(JSON.stringify(minInterval([[1,10]], [5])) === JSON.stringify([10]));
console.assert(JSON.stringify(minInterval([[1,5],[2,3]], [2,3])) === JSON.stringify([2,2]));
console.log("all tests pass");

Heaps / Priority Queues, running min-length heap with lazy deletion
Arrays, sorted intervals and queries

Difference Arrays, the boundary marking model for range updates and overlap counts.
Intervals, the range representation behind starts, ends, overlap, and coverage.

1851. Minimum Interval to Include Each Query (Hard)

Problem

Try it yourself

Approach 1: Brute force, per query, scan all intervals

Approach 2: Offline queries + min-heap (canonical)

Why offline sorting helps

Approach 3: Segment tree / merge sort tree

Summary

Test cases

Related data structures

Related concepts