135.Minimum Interval to Include Each Query

HardIntervals · 6/6

Problem

You are given a 2D array intervals where intervals[i] = [left_i, right_i] describes the inclusive interval from left_i to right_i. Its size is right_i - left_i + 1.

You are also given an array queries. For each queries[j], find the size of the smallest interval i with left_i <= queries[j] <= right_i. If no interval contains the query, the answer is -1. Return the answers in the original query order.

Examples

Input:  intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
Explanation:
- 2: [2,4] has size 3 (smallest containing 2).
- 3: [2,4] has size 3.
- 4: [4,4] has size 1.
- 5: only [3,6] contains it, size 4.

Input:  intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output: [2,-1,4,6]
Explanation: 19 is in no interval; 22 is only in [20,25] (size 6).

Constraints

1 <= intervals.length <= 10^5
1 <= queries.length <= 10^5
intervals[i].length == 2
1 <= left_i <= right_i <= 10^7
1 <= queries[j] <= 10^7

💡 Key Insight

Answer the queries offline in increasing order. Sort intervals by left endpoint; as the query value grows, push every interval that has started (left <= q) into a min-heap keyed by size. Intervals at the top that have already ended (right < q) can be popped permanently — later queries are even larger, so they will never contain them again. The heap top is then the smallest interval containing q.

Brute Force (Scan All Intervals per Query)

TimeO(n · q)SpaceO(1) besides the output.

Intuition

For every query, check every interval and keep the smallest size among those containing the query.

Algorithm

For each query q: best = infinity.
For each interval [l, r]: if l <= q <= r, best = min(best, r - l + 1).
Store best, or -1 if nothing matched.

Visualization

q = 5, intervals [1,4] [2,4] [3,6] [4,4]
[1,4]: 5 > 4 no    [2,4]: no    [3,6]: yes size 4    [4,4]: no
answer 4

Code

java

class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        int[] ans = new int[queries.length];
        for (int j = 0; j < queries.length; j++) {
            int q = queries[j];
            int best = Integer.MAX_VALUE;
            for (int[] in : intervals) {
                if (in[0] <= q && q <= in[1]) {
                    best = Math.min(best, in[1] - in[0] + 1);
                }
            }
            ans[j] = best == Integer.MAX_VALUE ? -1 : best;
        }
        return ans;
    }
}

Complexity

Time: O(n · q) — up to 10^10 checks at the limits, far too slow.
Space: O(1) besides the output.

Sort Intervals by Size + Early Exit

TimeO(n log n + n · q) worst caseSpaceO(n)

Intuition

If intervals are sorted from smallest to largest, the first interval that contains a query is automatically the answer, so each query can stop scanning as soon as it finds a match. This helps a lot when small intervals cover most queries, but a query contained in nothing (or only in the largest interval) still scans everything.

Algorithm

Sort intervals by size ascending.
For each query, scan in that order and return the size of the first interval with l <= q <= r.
If none matches, the answer is -1.

Visualization

sorted by size: [4,4](1) [2,4](3) [1,4](4) [3,6](4)
q = 3: [4,4] no -> [2,4] yes -> 3   (stops after 2 checks)
q = 5: [4,4] no -> [2,4] no -> [1,4] no -> [3,6] yes -> 4

Code

java

import java.util.Arrays;

class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        int[][] bySize = intervals.clone();
        Arrays.sort(bySize, (a, b) -> Integer.compare(a[1] - a[0], b[1] - b[0]));
        int[] ans = new int[queries.length];
        for (int j = 0; j < queries.length; j++) {
            int q = queries[j];
            ans[j] = -1;
            for (int[] in : bySize) {
                if (in[0] <= q && q <= in[1]) {
                    ans[j] = in[1] - in[0] + 1; // first match is the smallest
                    break;
                }
            }
        }
        return ans;
    }
}

Complexity

Time: O(n log n + n · q) worst case — the early exit does not help unmatched queries.
Space: O(n) — the sorted copy.

Sort + Sweep with a Min-HeapOptimal

TimeO(n log n + q log q)SpaceO(n + q)

Intuition

Process queries from smallest to largest while sweeping through intervals sorted by left endpoint:

Add every interval with left <= q to a min-heap ordered by (size, right). Once added, it stays a candidate for all bigger queries until it ends.
Lazily remove heap tops whose right < q. They can never contain this or any later query.
The remaining top (if any) contains q and is the smallest such interval.

Each interval is pushed once and popped at most once, so the sweep is O((n + q) log n). Remember each query's original index to write answers back in order.

Algorithm

Sort intervals by left. Sort query indices by query value.
i = 0; min-heap of [size, right].
For each query index idx in sorted order, with q = queries[idx]:
- While i < n and intervals[i][0] <= q: push [r - l + 1, r], i++.
- While heap top has right < q: pop.
- ans[idx] = heap empty ? -1 : top size.

Dry Run

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

flowchart TD
    Q2["q=2: push [1,4] s4, [2,4] s3<br/>top s3 r4, 4 >= 2 -> ans 3"] --> Q3["q=3: push [3,6] s4<br/>top s3 r4 still valid -> ans 3"]
    Q3 --> Q4["q=4: push [4,4] s1<br/>top s1 r4 valid -> ans 1"]
    Q4 --> Q5["q=5: pop s1 r4, pop s3 r4,<br/>pop s4 r4 (all ended)"]
    Q5 --> Q5b["top s4 r6 valid -> ans 4"]
    Q5b --> R["answers by original index: [3,3,1,4]"]

value:    1  2  3  4  5  6
[1,4]     [--------]
[2,4]        [-----]
[3,6]           [--------]
[4,4]              []
queries:     2  3  4  5

Code

java

import java.util.Arrays;
import java.util.PriorityQueue;

class Solution {
    public int[] minInterval(int[][] intervals, int[] queries) {
        int n = intervals.length, m = queries.length;
        int[][] sorted = intervals.clone();
        Arrays.sort(sorted, (a, b) -> Integer.compare(a[0], b[0])); // by left endpoint

        Integer[] order = new Integer[m]; // query indices sorted by value
        for (int j = 0; j < m; j++) {
            order[j] = j;
        }
        Arrays.sort(order, (a, b) -> Integer.compare(queries[a], queries[b]));

        // heap entry: [size, right]; smallest size first
        PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> a[0] != b[0] ? Integer.compare(a[0], b[0]) : Integer.compare(a[1], b[1]));
        int[] ans = new int[m];
        int i = 0;
        for (int idx : order) {
            int q = queries[idx];
            while (i < n && sorted[i][0] <= q) { // interval has started
                heap.offer(new int[] {sorted[i][1] - sorted[i][0] + 1, sorted[i][1]});
                i++;
            }
            while (!heap.isEmpty() && heap.peek()[1] < q) {
                heap.poll(); // ended before q: useless for all later queries
            }
            ans[idx] = heap.isEmpty() ? -1 : heap.peek()[0];
        }
        return ans;
    }
}

Complexity

Time: O(n log n + q log q) — two sorts, plus each interval pushed and popped at most once (O(log n) each).
Space: O(n + q) — the heap, sorted copy, and index array.

Complexity Comparison

Approach	Time	Space
Scan All Intervals per Query	O(n · q)	O(1)
Sort by Size + Early Exit	O(n log n + n · q)	O(n)
Sort + Sweep with Min-Heap	O(n log n + q log q)	O(n + q)

Common Pitfalls

Answering queries in sorted order but writing answers at the sorted position — store each query's original index.
Popping an interval because it doesn't contain the current query when it simply hasn't started yet — only push intervals with left <= q, and only pop those with right < q.
Forgetting the + 1 in size: intervals are inclusive, so [4,4] has size 1.
Duplicate query values: the heap logic handles them naturally, but a HashMap<value, answer> shortcut must not lose any original index.