Minimum Interval to Include Each Query
HardPrompt
You are given a 2D integer array intervals, where intervals[i] = [lefti, righti] describes the ith interval starting at lefti and ending at righti (inclusive). The size of an interval is defined as the number of integers it contains, or more formally righti - lefti + 1.
You are also given an integer array queries. The answer to the jth query is the size of the smallest interval i such that lefti <= queries[j] <= righti. If no such interval exists, the answer is -1.
Return an array containing the answers to the queries.
Example 1:
Input: intervals = [[1,4],[2,4],[3,6],[4,4]], queries = [2,3,4,5]
Output: [3,3,1,4]
Explanation: The queries are processed as follows:
- 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.Example 2:
Input: intervals = [[2,3],[2,5],[1,8],[20,25]], queries = [2,19,5,22]
Output: [2,-1,4,6]
Explanation: The queries are processed as follows:
- Query = 2: The interval [2,3] is the smallest interval containing 2. The answer is 3 - 2 + 1 = 2.
- Query = 19: None of the intervals contain 19. The answer is -1.
- Query = 5: The interval [2,5] is the smallest interval containing 5. The answer is 5 - 2 + 1 = 4.
- Query = 22: The interval [20,25] is the smallest interval containing 22. The answer is 25 - 20 + 1 = 6.
Constraints:
1 <= intervals.length <= 1051 <= queries.length <= 105intervals[i].length == 21 <= lefti <= righti <= 1071 <= queries[j] <= 107
Approaches
2 approaches with complexity analysis and trade-offs.
This is the most straightforward approach. For each query, we perform a linear scan through all the intervals. We check every single interval to see if it contains the query point. If it does, we calculate its size and compare it with the minimum size found so far for that specific query. We repeat this process for all queries.
Algorithm
- Initialize an
answersarray of the same size asqueries, filled with-1. - For each query
qat indexjinqueries: - Initialize
minSizeto a very large number (e.g.,Integer.MAX_VALUE). - Iterate through each interval
[left, right]in theintervalsarray. - Check if the interval contains the query:
left <= q <= right. - If it does, calculate its size
s = right - left + 1. - Update
minSize = min(minSize, s). - After checking all intervals, if
minSizewas updated, setanswers[j] = minSize. - Return the
answersarray.
Walkthrough
The brute-force method involves two nested loops. The outer loop iterates through each query in the queries array. For each query, the inner loop iterates through every interval in the intervals array. Inside the inner loop, we check if the current query value lies within the bounds of the current interval (left <= query <= right). If it does, we compute the interval's size (right - left + 1) and update a minSize variable if this new size is smaller. After the inner loop completes, the minSize variable will hold the size of the smallest interval containing the query. If no such interval was found, we assign -1. This result is stored in an answer array at the corresponding index of the query.
class Solution { public int[] minInterval(int[][] intervals, int[] queries) { int[] ans = new int[queries.length]; for (int i = 0; i < queries.length; i++) { int query = queries[i]; int minSize = Integer.MAX_VALUE; boolean found = false; for (int[] interval : intervals) { int left = interval[0]; int right = interval[1]; if (query >= left && query <= right) { int size = right - left + 1; minSize = Math.min(minSize, size); found = true; } } if (found) { ans[i] = minSize; } else { ans[i] = -1; } } return ans; }}Complexity
Time
O(N * M), where N is the number of intervals and M is the number of queries. For each of the M queries, we iterate through all N intervals, leading to a quadratic time complexity.
Space
O(M), where M is the number of queries. This space is used to store the result array. If the output array is not considered, the space complexity is O(1).
Trade-offs
Pros
Simple to understand and implement.
Requires minimal auxiliary data structures.
Cons
Extremely inefficient for large inputs.
Will cause a 'Time Limit Exceeded' (TLE) error on competitive programming platforms for the given constraints.
Solutions
Solution
class Solution {public int[] minInterval(int[][] intervals, int[] queries) { int n = intervals.length, m = queries.length; Arrays.sort(intervals, (a, b)->a[0] - b[0]); int[][] qs = new int[m][0]; for (int i = 0; i < m; ++i) { qs[i] = new int[]{queries[i], i}; } Arrays.sort(qs, (a, b)->a[0] - b[0]); int[] ans = new int[m]; Arrays.fill(ans, -1); PriorityQueue<int[]> pq = new PriorityQueue<>((a, b)->a[0] - b[0]); int i = 0; for (int[] q : qs) { while (i < n && intervals[i][0] <= q[0]) { int a = intervals[i][0], b = intervals[i][1]; pq.offer(new int[]{b - a + 1, b}); ++i; } while (!pq.isEmpty() && pq.peek()[1] < q[0]) { pq.poll(); } if (!pq.isEmpty()) { ans[q[1]] = pq.peek()[0]; } } return ans; }}Video walkthrough
Newsletter
One sharp idea, every week
System design and interview prep — short enough to finish.
No spam. Unsubscribe anytime.
Practice
Same difficulty — related problems to reinforce the pattern.