757. Set Intersection Size At Least Two
Problem Description
The problem requires us to find the smallest number of elements in a set that covers every given interval in a 2D array intervals, with the condition that each interval must have at least two elements from the set. An interval is represented by [start, end], which includes all integers between start and end inclusive.
To clarify, let's consider an example intervals = [[1,3], [2,5], [6,9]]: a valid containing set could be [1, 2, 4, 6, 7] as it has at least two numbers covered in every interval (for [1,3] it covers 1 and 2, for [2,5] it covers 2 and 4, and for [6,9] it covers 6 and 7). The goal is to find such a containing set that has the smallest possible number of elements.
Intuition
To arrive at the solution for this problem, we need to come up with a strategy that helps us minimize the number of elements in the containing set while ensuring that each interval has at least two elements from the set.
The intuition is to always pick the last two elements of an interval whenever possible, so as to maximize the chances of those elements being within the subsequent intervals. Sorting the intervals by their ending element in ascending order and, in case of a tie, by their starting element in descending order assists with this strategy. This ordering ensures that we process intervals in a manner that's optimal for choosing common elements.
The algorithm iterates through the sorted intervals and, for each interval, determines whether new elements need to be added to the containing set (nums). If an interval's start is greater than the last element (e) added to nums, then the interval is disjoint from the current containing set, and two new elements (b-1 and b) from this interval must be added to nums. If the interval's start is greater than the second-last element (s) but less than or equal to e, then the interval partially overlaps with the current containing set, and only one new element needs to be added (b). If an interval's start is less than or equal to s, it is fully covered by the current containing set, and no new elements are added.
The ans variable keeps track of the size of the containing set, incrementing by 2 when two elements are added and by 1 when one element is added. At the end, ans gives us the minimum size of a containing set that satisfies the problem's conditions.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
81public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
121class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85Solution Approach
The implementation of the solution in Python makes use of a greedy algorithm to minimize the size of the containing set.
The approach starts by sorting the intervals list. The sorting is done based on the end value of each interval in ascending order, using the lambda function key=lambda x: (x[1], -x[0]). This means that if we have two intervals with the same ending value, the one with the larger starting value will be considered first. Sorting the intervals this way prioritizes intervals that finish earlier, and for intervals with the same end, it prioritizes the wider range, which may encompass more of the following intervals.
After sorting, the algorithm initializes two pointers s and e with a value of -1 and a counter ans set to 0. These pointers track the last two elements that have been added to the containing set.
The algorithm iterates through each interval (a, b) in the sorted list of intervals. During each iteration, there are three scenarios to consider:
- The interval is already covered: If
a(start of the current interval) is less than or equal tos(second-to-last element added to the containing set), the current interval is already covered by the set, and we do not need to add any more elements. - Only one element of the interval is covered: If
a(start of the current interval) is greater thansbut less than or equal toe(last element added to the containing set), this means that the current interval overlaps with the last element, but we still need one more. So we increaseansby1, and updatestoeandetob(end of the current interval) to include the last two elements of the interval. - The interval is disjoint: If
a(start of the current interval) is greater thane(last element added to the containing set), then the current interval does not overlap with the elements in the set, and we must include its last two elements. Thus, we increaseansby2, and updatestob-1andetob, adding these two elements as the new last elements of the set.
After processing all intervals, the value of ans represents the size of the minimum containing set that fulfills the criteria outlined in the problem, which is returned at the end of the method.
This greedy solution is efficient because at each step it makes a locally optimal choice (adding as few elements as possible to cover the current interval) that leads to a globally optimal solution (minimal size of the containing set).
What is the best way of checking if an element exists in a sorted array once in terms of time complexity? Select the best that applies.
Example Walkthrough
Let's illustrate the solution approach with a small example where the given intervals is [[1,3], [2,4], [5,7]].
First, we apply the sorting strategy to the intervals list. The sorted intervals will be [[1,3], [2,4], [5,7]]. In this example, sorting doesn't change the order since the intervals are already in ascending order based on their end values.
Now, we initialize two pointers s and e to -1 and set the ans counter to 0. These variables help us track elements in the containing set and its size.
We start iterating through each interval (a, b) in the sorted list:
- The first interval is
[1,3]. Sinceais greater thane, this interval isn't covered by the containing set. So we add its last two elements{2, 3}to the set, incrementansby2, and updatesto2andeto3. - The set now covers
{2, 3}, andansis2.
Continuing with the second interval [2,4]:
- Here,
a (2)is equal tos (2), so one element of this interval is already covered. We need one more element from this interval to make sure we have two. Therefore, we add4, the last element, increasingansby1, and updatestoe (3)andeto4. - The set now covers
{2, 3, 4}, andansis3.
Next, we move on to the third interval [5,7]:
- For this interval,
a (5)is greater thane (4), signifying that the interval is disjoint from the set. We add the last two elements{6, 7}from this interval into the set, incrementansby2, and updatesto6andeto7. - The set now covers
{2, 3, 4, 6, 7}, andansis5.
Having processed all intervals, we can see that the smallest containing set that covers every given interval with at least two elements is {2, 3, 4, 6, 7} with a size of 5.
This walkthrough demonstrates how the greedy algorithm works step by step, adding as few elements as possible while ensuring each interval is covered by at least two elements from the set. The size of the final set, represented by ans, gives us the minimum number of elements required to satisfy the problem criteria.
Solution Implementation
1from typing import List
2
3class Solution:
4 def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
5 # Sort the intervals based on their ending values (primary) and
6 # starting values (secondary, in descending order).
7 intervals.sort(key=lambda x: (x[1], -x[0]))
8
9 # Initialize 'start' & 'end' to keep track of the last two elements
10 # in the current intersection set.
11 start = end = -1
12 # Initialize 'ans' to store the total number of elements in the intersection set.
13 ans = 0
14
15 # Iterate through each interval.
16 for current_start, current_end in intervals:
17 # If the current interval's start is less than or equal to 'start',
18 # it is already covered by the intersection set and we can skip it.
19 if current_start <= start:
20 continue
21
22 # If the current interval's start is greater than 'end',
23 # we need to add two new elements to cover this interval.
24 if current_start > end:
25 ans += 2
26 # Update 'start' and 'end' to the last two elements of this interval.
27 start, end = current_end - 1, current_end
28 else:
29 # If the current interval's start is within '[start, end]',
30 # we need to add only one new element to cover this interval.
31 ans += 1
32 # Update 'start' to 'end' and 'end' to the current interval's end.
33 start, end = end, current_end
34
35 # Return the total number of elements in the intersection set.
36 return ans
37
38# The solution class can now be used to instantiate an object and call the 'intersectionSizeTwo' method.
39# Here is how you can use it:
40
41sol = Solution()
42result = sol.intersectionSizeTwo([[1, 3], [4, 9], [0, 10]])
43print(result) # Example usage; should print out the result of the method call
441class Solution {
2 public int intersectionSizeTwo(int[][] intervals) {
3 // Sort the intervals based on their end value.
4 // If the end values are equal, sort based on start value in descending order.
5 Arrays.sort(intervals, (a, b) -> {
6 if (a[1] == b[1]) {
7 return b[0] - a[0];
8 }
9 return a[1] - b[1];
10 });
11
12 // Initialize answer as 0, and start/end as -1.
13 int answer = 0;
14 int start = -1, end = -1;
15
16 // Iterate over each interval.
17 for (int[] interval : intervals) {
18 int intervalStart = interval[0];
19 int intervalEnd = interval[1];
20
21 // If the current interval's start is less than or equal to the current `start`,
22 // it is already covered by the set of points we have.
23 if (intervalStart <= start) {
24 continue;
25 }
26
27 // If the current interval's start is greater than the current `end`,
28 // we need to add two points to cover this interval.
29 if (intervalStart > end) {
30 answer += 2;
31
32 // Update `start` and `end` to the last two elements of the interval.
33 start = intervalEnd - 1;
34 end = intervalEnd;
35 } else {
36 // If the current interval's start is within the range (start, end],
37 // we only need to add one more point to cover this interval.
38 answer += 1;
39
40 // Shift `start` to `end` and update `end` to the end of the current interval.
41 start = end;
42 end = intervalEnd;
43 }
44 }
45
46 // Return the minimum size of the set of points to cover all intervals.
47 return answer;
48 }
49}
501#include <vector>
2#include <algorithm>
3
4class Solution {
5public:
6 // Function to calculate the minimum size of a set so that for every
7 // interval in 'intervals' there are at least two distinct set elements which
8 // are in the interval.
9 int intersectionSizeTwo(std::vector<std::vector<int>>& intervals) {
10 // Sort the intervals based on their end points. If end points are the same,
11 // sort based on the start points in decreasing order. This way, we prefer
12 // intervals with larger start points for same end points.
13 sort(intervals.begin(), intervals.end(), [](const std::vector<int>& a, const std::vector<int>& b) {
14 return a[1] == b[1] ? a[0] > b[0] : a[1] < b[1];
15 });
16
17 int ans = 0; // Initialize the answer to 0.
18 int smallest = -1, secondSmallest = -1; // Initialize the two smallest elements seen so far to -1.
19
20 // Iterate through the sorted intervals
21 for (const auto& interval : intervals) {
22 int start = interval[0], end = interval[1];
23
24 // If the current start is less than or equal to smallest, this interval is already covered
25 // by the elements chosen so far.
26 if (start <= smallest) continue;
27
28 // If the current start is greater than secondSmallest, we need to add two more elements to the set.
29 if (start > secondSmallest) {
30 ans += 2;
31 // The secondSmallest is now the end of the interval minus one, and the smallest
32 // is the end of the interval.
33 secondSmallest = end - 1;
34 smallest = end;
35 } else {
36 // If start is between smallest and secondSmallest, we need to add one more element.
37 ans += 1;
38 // The new secondSmallest becomes the smallest we had, and the new smallest becomes the end of this interval.
39 secondSmallest = smallest;
40 smallest = end;
41 }
42 }
43
44 // Return the total number of elements added to the set.
45 return ans;
46 }
47};
481// Import statements are not required in TypeScript as they were in the C++ code.
2// Import statements for standard collections and algorithms are unnecessary in TypeScript.
3
4// Function to calculate the minimum size of a set so that for every
5// interval in 'intervals', there are at least two distinct set elements
6// that are within the interval.
7function intersectionSizeTwo(intervals: number[][]): number {
8 // Sort intervals by their end points. If end points are the same,
9 // sort by the start points in decreasing order. This ensures
10 // preference is given to intervals with larger start points for the same end points.
11 intervals.sort((a, b) => {
12 return a[1] === b[1] ? b[0] - a[0] : a[1] - b[1];
13 });
14
15 let answer = 0; // Initialize the answer to 0.
16 let smallest = -1, secondSmallest = -1; // Initialize the two smallest elements seen so far to -1.
17
18 // Iterate through the sorted intervals
19 for (const interval of intervals) {
20 const [start, end] = interval;
21
22 // If the current start is less than or equal to smallest, this interval is already covered
23 // by the elements chosen so far.
24 if (start <= smallest) continue;
25
26 // If the current start is greater than secondSmallest, we need to add two more elements to the set.
27 if (start > secondSmallest) {
28 answer += 2;
29 // secondSmallest is now end - 1, and smallest becomes end.
30 secondSmallest = end - 1;
31 smallest = end;
32 } else {
33 // If start is between smallest and secondSmallest, we need to add one more element.
34 answer += 1;
35 // New secondSmallest becomes the smallest we had before, and the new smallest becomes the end of this interval.
36 secondSmallest = smallest;
37 smallest = end;
38 }
39 }
40
41 // Return the total number of elements added to the set.
42 return answer;
43}
44How many ways can you arrange the three letters A, B and C?
Time and Space Complexity
Time Complexity
The time complexity of the given code is dominated by the sort operation applied to the list of intervals. Sorting a list of n intervals has a time complexity of O(n log n). After sorting, the code iterates over the sorted intervals once, which has a time complexity of O(n).
Thus, the total time complexity of the code is O(n log n) + O(n) which simplifies to O(n log n).
Space Complexity
The space complexity of the code is determined by the additional space used by the algorithm besides the input. The solution does not create any additional data structures that are dependent on the size of the input. The extra variables s, e, and ans use constant space.
Therefore, the space complexity of the code is O(1), which means it uses a constant amount of extra space.
Learn more about how to find time and space complexity quickly using problem constraints.
What's the output of running the following function using input [30, 20, 10, 100, 33, 12]?
1def fun(arr: List[int]) -> List[int]:
2 import heapq
3 heapq.heapify(arr)
4 res = []
5 for i in range(3):
6 res.append(heapq.heappop(arr))
7 return res
81public static int[] fun(int[] arr) {
2 int[] res = new int[3];
3 PriorityQueue<Integer> heap = new PriorityQueue<>();
4 for (int i = 0; i < arr.length; i++) {
5 heap.add(arr[i]);
6 }
7 for (int i = 0; i < 3; i++) {
8 res[i] = heap.poll();
9 }
10 return res;
11}
121class HeapItem {
2 constructor(item, priority = item) {
3 this.item = item;
4 this.priority = priority;
5 }
6}
7
8class MinHeap {
9 constructor() {
10 this.heap = [];
11 }
12
13 push(node) {
14 // insert the new node at the end of the heap array
15 this.heap.push(node);
16 // find the correct position for the new node
17 this.bubble_up();
18 }
19
20 bubble_up() {
21 let index = this.heap.length - 1;
22
23 while (index > 0) {
24 const element = this.heap[index];
25 const parentIndex = Math.floor((index - 1) / 2);
26 const parent = this.heap[parentIndex];
27
28 if (parent.priority <= element.priority) break;
29 // if the parent is bigger than the child then swap the parent and child
30 this.heap[index] = parent;
31 this.heap[parentIndex] = element;
32 index = parentIndex;
33 }
34 }
35
36 pop() {
37 const min = this.heap[0];
38 this.heap[0] = this.heap[this.size() - 1];
39 this.heap.pop();
40 this.bubble_down();
41 return min;
42 }
43
44 bubble_down() {
45 let index = 0;
46 let min = index;
47 const n = this.heap.length;
48
49 while (index < n) {
50 const left = 2 * index + 1;
51 const right = left + 1;
52
53 if (left < n && this.heap[left].priority < this.heap[min].priority) {
54 min = left;
55 }
56 if (right < n && this.heap[right].priority < this.heap[min].priority) {
57 min = right;
58 }
59 if (min === index) break;
60 [this.heap[min], this.heap[index]] = [this.heap[index], this.heap[min]];
61 index = min;
62 }
63 }
64
65 peek() {
66 return this.heap[0];
67 }
68
69 size() {
70 return this.heap.length;
71 }
72}
73
74function fun(arr) {
75 const heap = new MinHeap();
76 for (const x of arr) {
77 heap.push(new HeapItem(x));
78 }
79 const res = [];
80 for (let i = 0; i < 3; i++) {
81 res.push(heap.pop().item);
82 }
83 return res;
84}
85Recommended Readings
Greedy Introduction iframe width 560 height 315 src https www youtube com embed WTslqPbj7I title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture web share allowfullscreen iframe When do we use greedy Greedy algorithms tend to solve optimization problems Typically they will ask you
Sorting Summary Comparisons We presented quite a few sorting algorithms and it is essential to know the advantages and disadvantages of each one The basic algorithms are easy to visualize and easy to learn for beginner programmers because of their simplicity As such they will suffice if you don't know any advanced
Top Patterns to Conquer the Technical Coding Interview Should the written word bore you fear not A delightful video alternative awaits iframe width 560 height 315 src https www youtube com embed LW8Io6IPYHw title YouTube video player frameborder 0 allow accelerometer autoplay clipboard write encrypted media gyroscope picture in picture
Got a question? Ask the Teaching Assistant anything you don't understand.
Still not clear? Ask in the Forum, Discord or Submit the part you don't understand to our editors.