Leetcode 1851. Minimum Interval to Include Each Query

Problem Explanation

In this problem, you are given a 2D array of integer intervals, where each interval is defined as a range of integers from lefti to righti inclusive. The size of an interval is the number of integers it contains. You are also given a 1D array of queries, where each query asks for the smallest interval containing a given number (if exists).

The goal is to return an array of answers for each query, where each answer represents the size of the smallest interval containing the given number or -1 if there is no such interval.

Example Walkthrough

Let's walk through Example 1 provided in the problem description.

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

1. Prepare the input in form of priority queue and sorted queries.
2. Iterate through the sorted queries:
   • Query = 2: The interval [2,4] is the smallest interval containing 2. The answer is 4 - 2 + 1 = 3.
   • Query = 3: The interval [2,4] is the smallest interval containing 3. The answer is 4 - 2 + 1 = 3.
   • Query = 4: The interval [4,4] is the smallest interval containing 4. The answer is 4 - 4 + 1 = 1.
   • Query = 5: The interval [3,6] is the smallest interval containing 5. The answer is 6 - 3 + 1 = 4.

Final Output: [3,3,1,4]

Solution Approach

For solving this problem, we will use the priority queue data structure, sorting and two-pointer approach. This priority queue will help us in keeping track of the smallest intervals containing the given number. We will also sort the queries so that we can iterate through them in ascending order.

Solution in Python

1from typing import List
2from queue import PriorityQueue
3
4class Solution:
5    def minInterval(self, intervals: List[List[int]], queries: List[int]) -> List[int]:
6        # Initialize the answer list
7        ans = [-1] * len(queries)
8        
9        # Sort intervals and queries
10        intervals.sort()
11        qs = sorted([(query, idx) for idx, query in enumerate(queries)])
12
13        # Initialize priority queue
14        pq = PriorityQueue()
15
16        # Intervals pointer
17        i = 0
18        for query, idx in qs:
19            while i < len(intervals) and intervals[i][0] <= query:
20                size = intervals[i][1] - intervals[i][0] + 1
21                pq.put((size, intervals[i][1]))
22                i += 1
23            while not pq.empty() and pq.queue[0][1] < query:
24                pq.get()
25            if not pq.empty():
26                ans[idx] = pq.queue[0][0]
27
28        return ans

In this Python solution, we first sort the given intervals and queries, then initialize a priority queue to store the interval size and its right endpoint. We then iterate through the sorted queries while maintaining two pointers, one for intervals and the other for queries. We add any interval that starts before or at the current query to the priority queue and remove intervals whose right endpoint is before the current query. If the priority queue is not empty, we update the answer for the current query index with the smallest interval size in the queue.## Solution in JavaScript

1class PriorityQueue {
2    constructor() {
3        this.queue = [];
4    }
5
6    put(element) {
7        let added = false;
8        for (let i = 0; i < this.queue.length; i++) {
9            if (element[0] < this.queue[i][0]) {
10                this.queue.splice(i, 0, element);
11                added = true;
12                break;
13            }
14        }
15        if (!added) {
16            this.queue.push(element);
17        }
18    }
19
20    get() {
21        return this.queue.shift();
22    }
23
24    empty() {
25        return this.queue.length === 0;
26    }
27}
28
29var minInterval = function(intervals, queries) {
30    let ans = Array(queries.length).fill(-1);
31    intervals.sort((a, b) => a[0] - b[0]);
32    let qs = queries.map((q, idx) => [q, idx]).sort((a, b) => a[0] - b[0]);
33    
34    let pq = new PriorityQueue();
35    let i = 0;
36    for (let [query, idx] of qs) {
37        while (i < intervals.length && intervals[i][0] <= query) {
38            let size = intervals[i][1] - intervals[i][0] + 1;
39            pq.put([size, intervals[i][1]]);
40            i++;
41        }
42        while (!pq.empty() && pq.queue[0][1] < query) {
43            pq.get();
44        }
45        if (!pq.empty()) {
46            ans[idx] = pq.queue[0][0];
47        }
48    }
49    return ans;
50};

We use the same solution approach as Python implementation. Since JavaScript does not have a default priority queue implementation, we create a simple PriorityQueue class with put, get and empty methods. We also use the two-pointer approach to iterate through sorted queries while maintaining pointers for intervals and queries, updating the answer for the current query index with the smallest interval size in the priority queue.

Solution in Java

1import java.util.PriorityQueue;
2import java.util.Arrays;
3
4class Solution {
5    public int[] minInterval(int[][] intervals, int[] queries) {
6        int[] ans = new int[queries.length];
7        Arrays.fill(ans, -1);
8        Arrays.sort(intervals, (a, b) -> a[0] - b[0]);
9        
10        int[][] qs = new int[queries.length][2];
11        for (int i = 0; i < queries.length; i++) {
12            qs[i] = new int[] {queries[i], i};
13        }
14        Arrays.sort(qs, (a, b) -> a[0] - b[0]);
15        
16        PriorityQueue<int[]> pq = new PriorityQueue<>((a, b) -> a[0] - b[0]);
17        
18        int i = 0;
19        for (int[] query : qs) {
20            while (i < intervals.length && intervals[i][0] <= query[0]) {
21                int size = intervals[i][1] - intervals[i][0] + 1;
22                pq.offer(new int[]{size, intervals[i][1]});
23                i++;
24            }
25            while (!pq.isEmpty() && pq.peek()[1] < query[0]) {
26                pq.poll();
27            }
28            if (!pq.isEmpty()) {
29                ans[query[1]] = pq.peek()[0];
30            }
31        }
32        
33        return ans;
34    }
35}

The Java solution follows the same approach as the Python and JavaScript implementations. We first sort the intervals and queries and use a priority queue to store the interval size and its right endpoint. We iterate through the sorted queries while maintaining two pointers, one for intervals and the other for queries. We add any interval that starts before or at the current query to the priority queue and remove intervals whose right endpoint is before the current query. If the priority queue is not empty, we update the answer for the current query index with the smallest interval size in the queue.