Leetcode 757. Set Intersection Size At Least Two

Problem Explanation

The goal of this problem is to find the minimum size of a set S. This set has the property that for every interval A that exists in the intervals we have as input, the intersection of S with A should have at least 2 elements.

Example Walkthrough

For instance, let's take the example of intervals = [[1, 3], [1, 4], [2, 5], [3, 5]]. The set S could be {2, 3, 4}. It is easy to see that for each interval, there are at least 2 elements from S in the interval:

• [1, 3] intersect S gives {2, 3}
• [1, 4] intersect S gives {2, 3, 4}
• [2, 5] intersect S gives {2, 3, 4}
• [3, 5] intersect S gives {3, 4} And it's also easy to see that we can't obtain a smaller set than this, that satisfies the condition for all intervals.

Let's notice that S should contain numbers that appear in more intervals, to reduce its size. This is actually the core idea of the approach to solve this problem.

Solution Approach

To solve this problem, we first sort the intervals by their right end, and if two intervals have the same right end we sort them by their left end in descending order. This way the interval with the larger left end will come first and we have more chance to satisfy later intervals without adding more elements to the set S.

Java

1
2java
3class Solution {
4    public int intersectionSizeTwo(int[][] intervals) {
5        // Sorting the intervals based on two criteria.
6        Arrays.sort(intervals, (a, b) -> {
7            if (a[1] == b[1]) {
8                return b[0] - a[0];
9            } else {
10                return a[1] - b[1];
11            }
12        });
13
14        // Initializing variables.
15        int count = 2;
16        int lastOne = intervals[0][1];
17        int secondLastOne = lastOne - 1;
18        
19        // Iterating through the rest of intervals.
20        for (int i = 1; i < intervals.length; i++) {
21            // If the current interval is covered by the last two elements, we don't need to add anything to the set.
22            if (secondLastOne >= intervals[i][0]) {
23                continue;
24            }
25            // If the current interval is covered by the last one element, we only need to add one element to the set.
26            else if (lastOne >= intervals[i][0]) {
27                secondLastOne = lastOne;
28                lastOne = intervals[i][1];
29                count++;
30            }
31            // Otherwise, we need to add two elements to the set.
32            else {
33                secondLastOne = intervals[i][1] - 1;
34                lastOne = intervals[i][1];
35                count += 2;
36            }
37        }
38        
39        // Returning the size of the set.
40        return count;
41    }
42}

Python

1
2python
3class Solution:
4    def intersectionSizeTwo(self, intervals: List[List[int]]) -> int:
5        # Sorting the intervals based on two criteria.
6        intervals.sort(key=lambda x: (x[1], -x[0]))
7        
8        # Initializing variables.
9        count = 2
10        lastOne = intervals[0][1]
11        secondLastOne = lastOne - 1
12        
13        # Iterating through the rest of intervals.
14        for i in range(1, len(intervals)):
15            # If the current interval is covered by the last two elements, we don't need to add anything to the set.
16            if secondLastOne >= intervals[i][0]:
17                continue
18            # If the current interval is covered by the last one element, we only need to add one element to the set.
19            elif lastOne >= intervals[i][0]:
20                secondLastOne = lastOne
21                lastOne = intervals[i][1]
22                count += 1
23            # Otherwise, we need to add two elements to the set.
24            else:
25                secondLastOne = intervals[i][1] - 1
26                lastOne = intervals[i][1]
27                count += 2
28        
29        # Returning the size of the set.
30        return count

C#

1
2csharp
3public class Solution {
4    public int IntersectionSizeTwo(int[][] intervals) {
5        // Sorting the intervals based on two criteria.
6        Array.Sort(intervals, (a, b) => a[1] == b[1] ? b[0] - a[0] : a[1] - b[1]);
7        
8        // Initializing variables.
9        int count = 2;
10        int lastOne = intervals[0][1];
11        int secondLastOne = lastOne - 1;
12        
13        // Iterating through the rest of intervals.
14        for (int i = 1; i < intervals.Length; i++) {
15            // If the current interval is covered by the last two elements, we don't need to add anything to the set.
16            if (secondLastOne >= intervals[i][0]) {
17                continue;
18            }
19            // If the current interval is covered by the last one element, we only need to add one element to the set.
20            else if (lastOne >= intervals[i][0]) {
21                secondLastOne = lastOne;
22                lastOne = intervals[i][1];
23                count++;
24            }
25            // Otherwise, we need to add two elements to the set.
26            else {
27                secondLastOne = intervals[i][1] - 1;
28                lastOne = intervals[i][1];
29                count += 2;
30            }
31        }
32        
33        // Returning the size of the set.
34        return count;
35    }
36}

C++

1
2cpp
3class Solution {
4public:
5    int intersectionSizeTwo(vector<vector<int>>& intervals) {
6        // Sorting the intervals based on two criteria.
7        sort(intervals.begin(), intervals.end(), [](vector<int>& a, vector<int>& b) {
8            return a[1] < b[1] || (a[1] == b[1] && a[0] > b[0]);
9        });
10        
11        // Initializing variables.
12        int count = 2;
13        int lastOne = intervals[0][1];
14        int secondLastOne = lastOne - 1;
15        
16        // Iterating through the rest of intervals.
17        for (int i = 1; i < intervals.size(); i++) {
18            // If the current interval is covered by the last two elements, we don't need to add anything to the set.
19            if (secondLastOne >= intervals[i][0]) {
20                continue;
21            }
22            // If the current interval is covered by the last one element, we only need to add one element to the set.
23            else if (lastOne >= intervals[i][0]) {
24                secondLastOne = lastOne;
25                lastOne = intervals[i][1];
26                count++;
27            }
28            // Otherwise, we need to add two elements to the set.
29            else {
30                secondLastOne = intervals[i][1] - 1;
31                lastOne = intervals[i][1];
32                count += 2;
33            }
34        }
35        
36        // Returning the size of the set.
37        return count;
38    }
39};

Javascript

1
2javascript
3var intersectionSizeTwo = function(intervals) {
4    // Sorting the intervals based on two criteria.
5    intervals.sort(function(a, b) {
6        return a[1] == b[1] ? b[0] - a[0] : a[1] - b[1];
7    });
8    
9    // Initializing variables.
10    let count = 2;
11    let secondLastOne = intervals[0][1] - 1;
12    let lastOne = intervals[0][1];
13    
14    // Iterating through the rest of intervals.
15    for (let i = 1; i < intervals.length; i++) {
16        // If the current interval is covered by the last two elements, we don't need to add anything to the set.
17        if (secondLastOne >= intervals[i][0]) {
18            continue;
19        }
20        // If the current interval is covered by the last one element, we only need to add one element to the set.
21        else if (lastOne >= intervals[i][0]) {
22            secondLastOne = lastOne;
23            lastOne = intervals[i][1];
24            count++;
25        }
26        // Otherwise, we need to add two elements to the set.
27        else {
28            secondLastOne = intervals[i][1] - 1;
29            lastOne = intervals[i][1];
30            count += 2;
31        }
32    }
33    
34    // Returning the size of the set.
35    return count;
36};

Time and Space Complexity

The time complexity of the above problem is O(n log n) where n is the size of the intervals list due to sorting the list. The space complexity is O(1) as we are using a constant amount of space to store our result and temporary variables.## Rust

Rust is a systems programming language that runs extremely fast, prevents crashes, and denies null. This memory-safe language has syntax supporting advanced type checking to avoid as many programming errors as possible during compilation.

Let's define a solution using Rust:

1
2rust
3struct Solution;
4
5impl Solution {
6    pub fn intersection_size_two(intervals: Vec<Vec<i32>>) -> i32 {
7        let mut intervals = intervals;
8
9        // Sorting the intervals based on two criteria.
10        intervals.sort_by(|a, b| a[1].cmp(&b[1]).then_with(|| b[0].cmp(&a[0])));
11        
12        // Initializing variables.
13        let mut count = 2;
14        let mut lastOne = intervals[0][1];
15        let mut secondLastOne = lastOne - 1;
16        
17        // Iterating through the rest of intervals.
18        for i in 1..intervals.len() {
19            // If the current interval is covered by the last two elements, we don't need to add anything to the set.
20            if secondLastOne >= intervals[i][0] {
21                continue;
22            }
23            // If the current interval is covered by the last one element, we only need to add one element to the set.
24            else if lastOne >= intervals[i][0] {
25                secondLastOne = lastOne;
26                lastOne = intervals[i][1];
27                count += 1;
28            } 
29            // Otherwise, we need to add two elements to the set.
30            else {
31                secondLastOne = intervals[i][1] - 1;
32                lastOne = intervals[i][1];
33                count += 2;
34            }
35        }
36        
37        // Returning the size of the set.
38        count
39    }
40}

Kotlin

Kotlin is a programming language developed by Google for modern multi-platform applications. It's great for android developers as it simplifies common programming task and make code easy to read.

Here is solution in Kotlin:

1
2kotlin
3class Solution {
4    fun intersectionSizeTwo(intervals: Array<IntArray>): Int {
5        // Sorting the intervals based on two criteria.
6        intervals.sortWith(Comparator { a: IntArray, b: IntArray -> if (a[1] == b[1]) b[0] - a[0] else a[1] - b[1] })
7        
8        // Initializing variables.
9        var count = 2
10        var lastOne = intervals[0][1]
11        var secondLastOne = lastOne - 1
12        
13        // Iterating through the rest of intervals.
14        for (i in 1 until intervals.size) {
15            // If the current interval is covered by the last two elements, we don't need to add anything to the set.
16            if (secondLastOne >= intervals[i][0]) {
17                continue
18            } 
19            // If the current interval is covered by the last one element, we only need to add one element to the set.
20            else if (lastOne >= intervals[i][0]) {
21                secondLastOne = lastOne
22                lastOne = intervals[i][1]
23                count++
24            }
25            // Otherwise, we need to add two elements to the set.
26            else {
27                secondLastOne = intervals[i][1] - 1
28                lastOne = intervals[i][1]
29                count += 2
30            }
31        }
32        
33        // Returning the size of the set.
34        return count
35    }
36}

Conclusion

To solve the problem, we first sort the intervals by their right end. After sorting, we iterate over the intervals and check if they're already covered by the elements in the set. If the interval is covered, we continue to the next interval. If the interval is not fully covered, we add the necessary number of elements to the set. The final solution provided here is efficient, clean and works in different languages.