Skip to main content
CodePeetCodePeet
CodePeet 150

Minimum Interval to Include Each Query

HARDProblemSolveExternal Links

Description

You are given a 2D integer array intervals where intervals[i] = [left_i, right_i] represents an interval from left_i to right_i (inclusive on both ends). The size of an interval is the count of integers it contains, calculated as right_i - left_i + 1.

You are also given an integer array queries. For each query value queries[j], find the size of the smallest interval that contains queries[j]. An interval [left_i, right_i] contains a query value q when left_i <= q <= right_i.

If no interval contains a particular query value, the answer for that query is -1.

Return an array of answers where the jth element corresponds to the result of queries[j], preserving the original query order.

Examples

Example 1:

Input: intervals = [[1,3],[2,3],[3,7],[6,6]], queries = [2,3,1,7,6,8]

Output: [2,2,3,5,1,-1]

Explanation:

  • Query = 2: Intervals containing 2 are [1,3] (size 3) and [2,3] (size 2). Smallest size is 2.
  • Query = 3: Intervals containing 3 are [1,3] (size 3), [2,3] (size 2), and [3,7] (size 5). Smallest is 2.
  • Query = 1: Only [1,3] (size 3) contains 1. Answer is 3.
  • Query = 7: Only [3,7] (size 5) contains 7. Answer is 5.
  • Query = 6: [3,7] (size 5) and [6,6] (size 1) contain 6. Smallest is 1.
  • Query = 8: No interval contains 8. Answer is -1.

Example 2:

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

Output: [4,2,3,2]

Explanation:

  • Query = 4: [1,4] (size 4) and [3,6] (size 4) both contain 4. Smallest is 4.
  • Query = 2: [1,4] (size 4) and [2,3] (size 2) contain 2. Smallest is 2.
  • Query = 6: [3,6] (size 4) and [5,7] (size 3) contain 6. Smallest is 3.
  • Query = 3: [1,4] (size 4), [2,3] (size 2), and [3,6] (size 4) contain 3. Smallest is 2.

Constraints

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

Editorial

Brute Force

Intuition

The most straightforward way to solve this problem is to handle each query independently. For every query value q, we scan through all intervals and check whether q falls inside each one. If it does, we compute the interval's size and keep track of the smallest size we've seen.

Think of it like searching for the tightest-fitting glove. You have a collection of gloves (intervals) and a hand measurement (query). You try every glove, note which ones fit, and pick the smallest one that still covers your hand.

For each query:

  1. Start with min_size = infinity (no interval found yet).
  2. Loop through every interval [left, right].
  3. If left <= q <= right, the interval contains the query. Calculate its size as right - left + 1.
  4. Update min_size if this interval is smaller than the current best.
  5. After checking all intervals, if min_size is still infinity, no interval contained the query — return -1.

This approach requires no sorting or clever data structures, making it easy to understand and implement.

Step-by-Step

Let's trace through intervals = [[1,3],[2,3],[3,7],[6,6]] and two representative queries: q = 2 (found) and q = 8 (not found).

Query q = 2:

Step 1: Initialize min_size = ∞.

Step 2: Check interval [1,3]: Is 1 <= 2 <= 3? YES. Size = 3 - 1 + 1 = 3. Update min_size = 3.

Step 3: Check interval [2,3]: Is 2 <= 2 <= 3? YES. Size = 3 - 2 + 1 = 2. Since 2 < 3, update min_size = 2.

Step 4: Check interval [3,7]: Is 3 <= 2? NO (3 > 2). This interval starts after query 2. Skip.

Step 5: Check interval [6,6]: Is 6 <= 2? NO (6 > 2). Skip.

Step 6: All intervals checked. min_size = 2. Answer for query 2 is 2 (from interval [2,3]).

Query q = 8:

Step 7: Initialize min_size = ∞.

Step 8: Check [1,3]: Is 8 <= 3? NO. Query 8 is past the right end.

Step 9: Check [2,3]: Is 8 <= 3? NO. Same issue.

Step 10: Check [3,7]: Is 8 <= 7? NO. Close, but 8 extends past.

Step 11: Check [6,6]: Is 8 <= 6? NO.

Step 12: All intervals checked. min_size is still ∞. No interval contains 8. Answer is -1.

Notice we performed 4 interval checks per query. With n intervals and m queries, that's n × m total checks.

Set up brute force for query q=2 — Set up brute force for query q=2. Show all intervals on the number line with the query marker.

Algorithm

  1. Initialize a result array of size m (number of queries), filled with -1.
  2. For each query queries[j]:
    • Set min_size = infinity.
    • For each interval [left, right]:
      • If left <= queries[j] <= right, compute size = right - left + 1.
      • Update min_size = min(min_size, size).
    • If min_size != infinity, set result[j] = min_size.
  3. Return the result array.

Code

class Solution {
public:
    vector<int> minInterval(vector<vector<int>>& intervals,
                            vector<int>& queries) {
        int n = intervals.size();
        int m = queries.size();
        vector<int> result(m, -1);

        for (int j = 0; j < m; j++) {
            int minSize = INT_MAX;
            for (int i = 0; i < n; i++) {
                if (intervals[i][0] <= queries[j] &&
                    queries[j] <= intervals[i][1]) {
                    int size = intervals[i][1] - intervals[i][0] + 1;
                    minSize = min(minSize, size);
                }
            }
            if (minSize != INT_MAX) {
                result[j] = minSize;
            }
        }
        return result;
    }
};
class Solution:
    def minInterval(self, intervals: List[List[int]],
                    queries: List[int]) -> List[int]:
        result = []
        for q in queries:
            min_size = float('inf')
            for left, right in intervals:
                if left <= q <= right:
                    size = right - left + 1
                    min_size = min(min_size, size)
            result.append(
                min_size if min_size != float('inf')
                else -1
            )
        return result
class Solution {
    public int[] minInterval(int[][] intervals,
                             int[] queries) {
        int n = intervals.length;
        int m = queries.length;
        int[] result = new int[m];
        Arrays.fill(result, -1);

        for (int j = 0; j < m; j++) {
            int minSize = Integer.MAX_VALUE;
            for (int i = 0; i < n; i++) {
                if (intervals[i][0] <= queries[j] &&
                    queries[j] <= intervals[i][1]) {
                    int size = intervals[i][1] - intervals[i][0] + 1;
                    minSize = Math.min(minSize, size);
                }
            }
            if (minSize != Integer.MAX_VALUE) {
                result[j] = minSize;
            }
        }
        return result;
    }
}

Complexity

Time Complexity: O(n × m) where n is the number of intervals and m is the number of queries.

For each of the m queries, we scan through all n intervals. Each check is O(1), so the total work is n × m.

Space Complexity: O(m)

We only need the result array of size m. No additional data structures are used beyond a few variables.

Why This Approach Is Not Efficient

The brute force performs n × m interval checks. With the given constraints (n and m up to 10^5), this means up to 10^10 operations — far beyond what can complete within typical time limits (usually around 10^8 operations per second).

The fundamental inefficiency is that we re-examine every interval from scratch for each query. If query 2 already determined that [1,3] and [2,3] contain the point, we throw away that knowledge when processing query 3. We start over from interval index 0 every time.

Key insight: If we sort both the intervals and queries, we can process them in a single sweep. As we move from smaller query values to larger ones, intervals only need to be considered once — they're either added to our candidate set (when their left endpoint is reached) or removed from it (when their right endpoint is passed). This observation leads to the optimal approach using a min-heap to efficiently track the smallest valid interval at each point.

Bar chart comparing brute force O(n×m) = 10^10 operations versus sort + min-heap O(n log n + m log m) ≈ 3.3 × 10^6 operations for n = m = 10^5
Bar chart comparing brute force O(n×m) = 10^10 operations versus sort + min-heap O(n log n + m log m) ≈ 3.3 × 10^6 operations for n = m = 10^5

Optimal Approach - Sort + Min-Heap

Intuition

The crucial observation is that the order in which we answer queries doesn't affect the final result — we just need to return answers in the original order. This means we can sort the queries and process them in ascending order, which unlocks a powerful optimization.

Imagine a sweep line moving from left to right across the number line. As the sweep line reaches each query point:

  1. Add intervals whose left endpoint is ≤ the current query value. These intervals have "started" and could potentially contain the query.
  2. Remove intervals whose right endpoint is < the current query value. These intervals have "ended" before the query point, so they're no longer valid.
  3. Answer the query using the smallest remaining valid interval.

To efficiently find the smallest valid interval at each step, we use a min-heap ordered by interval size. The heap always has the smallest interval at the top, so answering each query is an O(1) peek operation.

The beauty of this approach is that each interval is pushed onto the heap exactly once (when its left endpoint is reached) and popped at most once (when it expires). Sorting allows us to process intervals incrementally rather than re-scanning them for every query.

Sweep line diagram showing sorted queries processed left to right, with intervals being added to and removed from a min-heap as the sweep progresses
Sweep line diagram showing sorted queries processed left to right, with intervals being added to and removed from a min-heap as the sweep progresses

Step-by-Step

Let's trace through intervals = [[1,3],[2,3],[3,7],[6,6]] and queries = [2,3,1,7,6,8].

Preprocessing:

  • Sort intervals by left endpoint: [[1,3],[2,3],[3,7],[6,6]] (already sorted).
  • Sort queries by value, preserving original indices: [(1,idx2), (2,idx0), (3,idx1), (6,idx4), (7,idx3), (8,idx5)].
  • Initialize empty min-heap and interval pointer i = 0.

Process query (1, idx=2):

  • Add intervals with left ≤ 1: [1,3] → push (size=3, right=3).
  • Remove expired (right < 1): none.
  • Heap top = (3, 3) → result[2] = 3.

Process query (2, idx=0):

  • Add intervals with left ≤ 2: [2,3] → push (size=2, right=3).
  • Heap: [(2,3), (3,3)].
  • Remove expired (right < 2): none.
  • Heap top = (2, 3) → result[0] = 2.

Process query (3, idx=1):

  • Add intervals with left ≤ 3: [3,7] → push (size=5, right=7).
  • Heap: [(2,3), (3,3), (5,7)].
  • Remove expired (right < 3): none.
  • Heap top = (2, 3) → result[1] = 2.

Process query (6, idx=4):

  • Add intervals with left ≤ 6: [6,6] → push (size=1, right=6).
  • Remove expired (right < 6): pop (2,3) and (3,3) — both have right=3 < 6.
  • Heap after cleanup: [(1,6), (5,7)].
  • Heap top = (1, 6) → result[4] = 1.

Process query (7, idx=3):

  • No new intervals to add.
  • Remove expired (right < 7): pop (1,6) — right=6 < 7.
  • Heap: [(5,7)].
  • Heap top = (5, 7) → result[3] = 5.

Process query (8, idx=5):

  • No new intervals to add.
  • Remove expired (right < 8): pop (5,7) — right=7 < 8.
  • Heap is empty → result[5] = -1.

Final answer: [2, 2, 3, 5, 1, -1].

Initialize empty min-heap — Initialize empty min-heap. Sort intervals and queries for sweep-line processing.

Algorithm

  1. Sort the intervals array by left endpoint.
  2. Create an indexed version of queries: (value, original_index) pairs, then sort by value.
  3. Initialize a result array of size m filled with -1, an empty min-heap, and an interval pointer i = 0.
  4. For each sorted query (val, idx):
    • Add relevant intervals: While i < n and intervals[i][0] <= val, push (size, right) onto the min-heap where size = right - left + 1. Increment i.
    • Remove expired intervals: While the heap is non-empty and the top entry's right endpoint < val, pop from the heap.
    • Record answer: If the heap is non-empty, result[idx] = heap_top.size.
  5. Return the result array.

Code

class Solution {
public:
    vector<int> minInterval(vector<vector<int>>& intervals,
                            vector<int>& queries) {
        int n = intervals.size();
        int m = queries.size();
        vector<int> result(m, -1);

        sort(intervals.begin(), intervals.end());

        vector<pair<int,int>> sortedQueries;
        for (int i = 0; i < m; i++) {
            sortedQueries.push_back({queries[i], i});
        }
        sort(sortedQueries.begin(),
             sortedQueries.end());

        priority_queue<pair<int,int>,
                       vector<pair<int,int>>,
                       greater<>> minHeap;
        int i = 0;

        for (auto& [val, idx] : sortedQueries) {
            while (i < n && intervals[i][0] <= val) {
                int size = intervals[i][1]
                         - intervals[i][0] + 1;
                minHeap.push({size, intervals[i][1]});
                i++;
            }
            while (!minHeap.empty() &&
                   minHeap.top().second < val) {
                minHeap.pop();
            }
            if (!minHeap.empty()) {
                result[idx] = minHeap.top().first;
            }
        }
        return result;
    }
};
class Solution:
    def minInterval(self, intervals: List[List[int]],
                    queries: List[int]) -> List[int]:
        intervals.sort()
        sorted_queries = sorted(
            (val, idx)
            for idx, val in enumerate(queries)
        )
        result = [-1] * len(queries)
        heap = []
        i = 0

        for val, idx in sorted_queries:
            while (i < len(intervals) and
                   intervals[i][0] <= val):
                left, right = intervals[i]
                heappush(heap,
                         (right - left + 1, right))
                i += 1
            while heap and heap[0][1] < val:
                heappop(heap)
            if heap:
                result[idx] = heap[0][0]

        return result
class Solution {
    public int[] minInterval(int[][] intervals,
                             int[] queries) {
        int n = intervals.length;
        int m = queries.length;
        int[] result = new int[m];
        Arrays.fill(result, -1);

        Arrays.sort(intervals,
                    (a, b) -> a[0] - b[0]);

        int[][] sortedQueries = new int[m][2];
        for (int j = 0; j < m; j++) {
            sortedQueries[j] =
                new int[]{queries[j], j};
        }
        Arrays.sort(sortedQueries,
                    (a, b) -> a[0] - b[0]);

        PriorityQueue<int[]> minHeap =
            new PriorityQueue<>(
                (a, b) -> a[0] - b[0]);
        int i = 0;

        for (int[] q : sortedQueries) {
            int val = q[0], idx = q[1];
            while (i < n &&
                   intervals[i][0] <= val) {
                int size = intervals[i][1]
                         - intervals[i][0] + 1;
                minHeap.offer(
                    new int[]{size,
                              intervals[i][1]});
                i++;
            }
            while (!minHeap.isEmpty() &&
                   minHeap.peek()[1] < val) {
                minHeap.poll();
            }
            if (!minHeap.isEmpty()) {
                result[idx] = minHeap.peek()[0];
            }
        }
        return result;
    }
}

Complexity

Time Complexity: O(n log n + m log m)

Sorting intervals takes O(n log n) and sorting queries takes O(m log m). The main loop processes each query once. Across all iterations, each interval is pushed onto the heap exactly once and popped at most once, giving at most n pushes and n pops. Each heap operation costs O(log n), so total heap work is O(n log n). The overall complexity is O(n log n + m log m).

Space Complexity: O(n + m)

The sorted queries array uses O(m) space, the result array uses O(m), and the min-heap can hold at most n intervals at once, costing O(n). Total: O(n + m).