#1851 Minimum Interval to Include Each Query
frequently reported atGoogle
the problem
In plain words
intervals[i] = [left, right] covers every integer from left to right, and its size is right − left + 1. For each queries[j], find the size of the smallest interval that contains queries[j], or −1 if none does. Return the answers in the queries' original order.
in intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
out [3,3,1,4]
2 → [2,4] (size 3). 3 → [2,4] (3). 4 → [4,4] (1). 5 → [3,6] (4).
in intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
out [2,-1,4,6]
Nothing contains 19.
- 1 ≤ intervals.length ≤ 10⁵
- 1 ≤ queries.length ≤ 10⁵
- 1 ≤ left ≤ right ≤ 10⁷
- 1 ≤ queries[j] ≤ 10⁷
your turn
Try it before you peek
Read the examples, say the brute force out loud, then write code: here or on LeetCode ↗. Stuck for 20 minutes? Open one hint at a time.
Solve it in the browser
LeetCode-style: complete the class. Compiled by the real javac (Java 17) and judged right here — nothing is sent anywhere.
Solutions are hidden so you can try first. Even 20 minutes of real effort makes the answer stick far better than reading it.
Marking the problem solved, or opening every hint, also shows it.
the aha
Key insight
patternSweep line & difference arrayGreedy with a heap
Answer the queries in increasing order, not the given order. Then each interval becomes useful once (left ≤ q) and useless forever once (right < q). A min-heap by size, cleaned lazily, always has the answer on top.
solutions
From brute force to optimal
For each query, scan all intervals and keep the smallest one that contains it.
- For each query q: best = ∞.
- For each interval with left ≤ q ≤ right: best = min(best, size).
- Answer best, or −1.
Every query scans every interval: up to 10¹⁰ steps at the limits.
Besides the answer array.
class Solution { public int[] minInterval(int[][] intervals, int[] queries) { int[] ans = new int[queries.length]; for (int j = 0; j < queries.length; j++) { int best = Integer.MAX_VALUE; for (int[] iv : intervals) { if (iv[0] <= queries[j] && queries[j] <= iv[1]) best = Math.min(best, iv[1] - iv[0] + 1); } ans[j] = best == Integer.MAX_VALUE ? -1 : best; } return ans; }}Sort intervals by left and query positions by value. For each query, push every interval that has started, drop the ones that have ended, and read the smallest size.
- Sort intervals by left; sort an index array of the queries by value.
- For each query q in increasing order: push (size, right) for every interval with left ≤ q.
- Pop while the top's right < q; the answer is the top's size, or −1.
Two sorts, and each interval is pushed and popped at most once, O(log n) each.
The heap and the sorted copies.
class Solution { public int[] minInterval(int[][] intervals, int[] queries) { int[][] byLeft = intervals.clone(); Arrays.sort(byLeft, (a, b) -> Integer.compare(a[0], b[0])); Integer[] order = new Integer[queries.length]; // answer queries smallest first, for (int j = 0; j < order.length; j++) order[j] = j; // but remember where each one goes Arrays.sort(order, (a, b) -> Integer.compare(queries[a], queries[b])); // heap of {size, right}: the smallest interval that has started is on top PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0])); int[] ans = new int[queries.length]; int i = 0; for (int j : order) { int q = queries[j]; while (i < byLeft.length && byLeft[i][0] <= q) { // every interval starting by q joins heap.offer(new int[] {byLeft[i][1] - byLeft[i][0] + 1, byLeft[i][1]}); i++; } while (!heap.isEmpty() && heap.peek()[1] < q) heap.poll(); // ended before q: useless for every later q too ans[j] = heap.isEmpty() ? -1 : heap.peek()[0]; } return ans; }}Handle intervals from smallest to largest. Each one answers every still-waiting query inside it; those queries are done for good.
- Sort intervals by size; put query values in a TreeMap value → positions.
- For each interval, repeatedly take ceilingEntry(left) while its key ≤ right: answer those positions, remove the key.
- Unanswered queries stay −1.
The sort, one ceiling lookup per interval, and each query value removed once.
The TreeMap of waiting queries.
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])); // smallest first TreeMap<Integer, List<Integer>> waiting = new TreeMap<>(); // query value -> its positions for (int j = 0; j < queries.length; j++) waiting.computeIfAbsent(queries[j], k -> new ArrayList<>()).add(j); int[] ans = new int[queries.length]; Arrays.fill(ans, -1); for (int[] iv : bySize) { // every still-waiting query inside [left, right] gets this size: nothing smaller is left Map.Entry<Integer, List<Integer>> e = waiting.ceilingEntry(iv[0]); while (e != null && e.getKey() <= iv[1]) { for (int j : e.getValue()) ans[j] = iv[1] - iv[0] + 1; waiting.remove(e.getKey()); // answered for good e = waiting.ceilingEntry(iv[0]); } } return ans; }}in the room
How to say it in the interview
talk track
- Brute force is n × q, up to 10¹⁰: too slow, so sort something.
- Say the offline trick: "I'll answer the queries in sorted order and write each answer back to its original index."
- Sweep: push intervals that have started into a min-heap by size, pop the ones that have ended, read the top.
- Explain why lazy deletion is safe: queries only move right, so an ended interval never helps again.
traps
- Losing the original order: sort an
Integer[]of positions, not the queries array itself. - Popping just once: keep popping while the top's right end < q.
- Forgetting repeated query values: each position needs its own answer.
what they ask next
Follow-ups
What if queries arrive one at a time (online)?
The sweep needs every query up front. Online, compress the coordinates and use a segment tree where each interval lowers the minimum size over its range; a point query then reads the minimum along one root-to-leaf path in O(log n).
Return the interval itself, not its size?
Store the interval's index in the heap entry and return that.
before you submit
Edge cases to test
- No interval contains the query → −1.
- Repeated query values → each position gets the same answer.
- A small interval that ended before q sits on top of the heap: pop it, don't use it.
- Coordinates up to 10⁷: too big for a plain array per point, fine for sorting.
practise next
Similar problems
- #253Meeting Rooms IIMediumin IntervalsLeetCode Premium
- #759Employee Free TimeHardin IntervalsLeetCode Premium
- #973K Closest Points to OriginMediumin Heaps