Minimum Interval to Include Each Query

Hard
1426.

Minimum Interval to Include Each Query

HardArrayBinary SearchSortingHeap (Priority Queue)GoogleAmazon

Minimum Interval to Include Each Query is a hard coding problem on arrays, sorting and binary search, asked in Amazon and Google interviews.

Each intervals[i] = [left, right] covers the integers from left to right, both included; its size is right - left + 1.

For every queries[j], find the smallest size of an interval that contains the value queries[j] (left <= queries[j] <= right). If no interval contains it, the answer is -1.

Return the answers as an array in the order of queries.

Example 1

Input
intervals = [[2,5],[4,4],[6,9],[1,10]], queries = [4,3,8,11]
Output
[1,4,4,-1]
Explanation
4 lies in [4,4] (size 1); 3 in [2,5] (size 4); 8 in [6,9] (size 4); nothing reaches 11.

Example 2

Input
intervals = [[1,3],[3,7]], queries = [3,1,9]
Output
[3,3,-1]

Constraints

  • 1 <= intervals.length <= 10^5
  • 1 <= queries.length <= 10^5
  • intervals[i].length == 2
  • 1 <= left <= right <= 10^7
  • 1 <= queries[j] <= 10^7
Write your solution here. Running it against the tests needs a free account — what you type comes with you.Sign in to run
/**
 * @param {number[][]} intervals
 * @param {number[]} queries
 * @return {number[]}
 */
var minInterval = function(intervals, queries) {
    // Write your code here
    
};

Sign in to run your own test cases

Sign in

Minimum Interval to Include Each Query — Problem & Solution

Minimum Interval to Include Each Query solution explained: step-by-step approach, complexity and code in Python, Java, C++ and JavaScript. A hard problem.

Minimum Interval to Include Each Query is a hard coding problem on arrays, sorting and binary search, asked in Amazon and Google interviews.

  • Difficulty: Hard
  • Topics: Arrays, Sorting, Binary Search, Heap
  • Asked at: Amazon, Google
  • Time limit: 2 s
  • Memory limit: 256 MB
  • Languages: JavaScript, TypeScript, Python, Java, C++, C, C#, Go, Kotlin, Swift, Rust, PHP and Ruby

Problem statement

Each intervals[i] = [left, right] covers the integers from left to right, both included; its size is right - left + 1.

For every queries[j], find the smallest size of an interval that contains the value queries[j] (left <= queries[j] <= right). If no interval contains it, the answer is -1.

Return the answers as an array in the order of queries.

Example 1

Input: intervals = [[2,5],[4,4],[6,9],[1,10]], queries = [4,3,8,11]
Output: [1,4,4,-1]
Explanation: 4 lies in [4,4] (size 1); 3 in [2,5] (size 4); 8 in [6,9] (size 4); nothing reaches 11.

Example 2

Input: intervals = [[1,3],[3,7]], queries = [3,1,9]
Output: [3,3,-1]

Constraints

  • 1 <= intervals.length <= 10^5
  • 1 <= queries.length <= 10^5
  • intervals[i].length == 2
  • 1 <= left <= right <= 10^7
  • 1 <= queries[j] <= 10^7

Hints for Minimum Interval to Include Each Query

  1. Hint 1

    Answering queries in increasing order lets you reuse work: an interval that has started for one query has started for all later ones.

  2. Hint 2

    Sort intervals by left and add each to a pool once its left is at most the current query.

  3. Hint 3

    Keep the pool in a min-heap by size; before reading the top, discard tops whose right is already below the query — they can never contain a later query either.

How to solve Minimum Interval to Include Each Query

Process the queries offline in increasing order. Intervals enter a min-heap (keyed by size) as soon as they start, and leave it lazily once they end — for sorted queries an ended interval stays ended, so throwing it away is safe.

Approach

  1. Sort the intervals by left, and sort the query indices by query value.
  2. For each query q in that order, push every not-yet-pushed interval with left <= q into a min-heap keyed by (size, right).
  3. Pop the top while its right < q.
  4. The answer for q is the top's size, or -1 if the heap is empty; store it at the query's original index.

Why it works

When q is answered, the heap holds every interval with left <= q except some with right < q' for an earlier q' <= q, which cannot contain q. After popping, the top has right >= q and left <= q, so it contains q, and its size is minimal among all heap members — in particular among all intervals containing q, since none of those was discarded.

Complexity

  • Time — O(n log n + m log m)
  • Space — O(n + m)

Pitfalls

  • Answers must come back in the original query order — sort indices, not the values themselves.
  • Only the top is checked for expiry; that is enough because a stale entry deeper down is popped the moment it surfaces.
  • Both ends are inclusive: the size is right - left + 1 and an interval with right == q still counts.

Reference solution

Python

from typing import List
import heapq

def minInterval(intervals: List[List[int]], queries: List[int]) -> List[int]:
    ivs = sorted(intervals)
    order = sorted(range(len(queries)), key=lambda j: queries[j])
    ans = [-1] * len(queries)
    heap = []  # (size, right) of started intervals
    at = 0
    for j in order:
        q = queries[j]
        while at < len(ivs) and ivs[at][0] <= q:
            heapq.heappush(heap, (ivs[at][1] - ivs[at][0] + 1, ivs[at][1]))
            at += 1
        while heap and heap[0][1] < q:
            heapq.heappop(heap)
        if heap:
            ans[j] = heap[0][0]
    return ans

Java

public static int[] minInterval(int[][] intervals, int[] queries) {
    int[][] ivs = intervals.clone();
    Arrays.sort(ivs, (a, b) -> Integer.compare(a[0], b[0]));
    Integer[] order = new Integer[queries.length];
    for (int j = 0; j < queries.length; j++) order[j] = j;
    Arrays.sort(order, (a, b) -> Integer.compare(queries[a], queries[b]));
    // (size, right) of started intervals, smallest size on top
    PriorityQueue<int[]> heap = new PriorityQueue<>((a, b) -> Integer.compare(a[0], b[0]));
    int[] ans = new int[queries.length];
    int at = 0;
    for (int j : order) {
        int q = queries[j];
        while (at < ivs.length && ivs[at][0] <= q) {
            heap.add(new int[] { ivs[at][1] - ivs[at][0] + 1, ivs[at][1] });
            at++;
        }
        while (!heap.isEmpty() && heap.peek()[1] < q) heap.poll();
        ans[j] = heap.isEmpty() ? -1 : heap.peek()[0];
    }
    return ans;
}

C++

vector<int> minInterval(vector<vector<int>>& intervals, vector<int>& queries) {
    vector<vector<int>> ivs = intervals;
    sort(ivs.begin(), ivs.end());
    vector<int> order(queries.size());
    for (int j = 0; j < (int) queries.size(); j++) order[j] = j;
    sort(order.begin(), order.end(), [&](int a, int b) { return queries[a] < queries[b]; });
    // (size, right) of started intervals, smallest size on top
    priority_queue<pair<int, int>, vector<pair<int, int>>, greater<pair<int, int>>> heap;
    vector<int> ans(queries.size(), -1);
    size_t at = 0;
    for (int j : order) {
        int q = queries[j];
        while (at < ivs.size() && ivs[at][0] <= q) {
            heap.push({ivs[at][1] - ivs[at][0] + 1, ivs[at][1]});
            at++;
        }
        while (!heap.empty() && heap.top().second < q) heap.pop();
        if (!heap.empty()) ans[j] = heap.top().first;
    }
    return ans;
}

JavaScript

var minInterval = function(intervals, queries) {
    var ivs = intervals.slice().sort(function(a, b) { return a[0] - b[0]; });
    var order = [];
    for (var j = 0; j < queries.length; j++) order.push(j);
    order.sort(function(a, b) { return queries[a] - queries[b]; });
    var SHIFT = 16777216; // 2^24: sizes and right ends both stay below it
    var heap = []; // min-heap of size * SHIFT + right
    var ans = [];
    for (var z = 0; z < queries.length; z++) ans.push(-1);
    var at = 0;
    for (var t = 0; t < order.length; t++) {
        var q = queries[order[t]];
        while (at < ivs.length && ivs[at][0] <= q) {
            heapPush(heap, (ivs[at][1] - ivs[at][0] + 1) * SHIFT + ivs[at][1]);
            at++;
        }
        while (heap.length > 0 && heap[0] % SHIFT < q) heapPop(heap);
        if (heap.length > 0) ans[order[t]] = Math.floor(heap[0] / SHIFT);
    }
    return ans;
};

var heapPush = function(h, v) {
    h.push(v);
    var i = h.length - 1;
    while (i > 0) {
        var p = (i - 1) >> 1;
        if (h[p] <= h[i]) break;
        var t = h[p]; h[p] = h[i]; h[i] = t;
        i = p;
    }
};

var heapPop = function(h) {
    var top = h[0];
    var last = h.pop();
    if (h.length > 0) {
        h[0] = last;
        var j = 0;
        for (;;) {
            var l = 2 * j + 1, r = l + 1, s = j;
            if (l < h.length && h[l] < h[s]) s = l;
            if (r < h.length && h[r] < h[s]) s = r;
            if (s === j) break;
            var t = h[s]; h[s] = h[j]; h[j] = t;
            j = s;
        }
    }
    return top;
};

Also on the editorial tab: C, C#, Go, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

All 1199 arrays problems · the whole catalogue

Learn the technique: Arrays · Sorting Algorithms