Number of Intersecting Interval Pairs II solution and explanation
6 more videos on this problem
Number of Intersecting Interval Pairs II | Sorting & Binary Search| Leetcode Contest | Leetcode 4057Sanyam IIT Guwahati · 10:00 · 598 views
Leetcode 4057 | Number of Intersecting Interval Pairs II | Leetcode weekly contest 520CodeWithMeGuys · 10:48 · 331 views
Number of Intersecting Interval Pairs II | Sorting + Sliding WindowManjeet Dhayal · 4:58 · 329 views
4057. Number of Intersecting Interval Pairs II (Leetcode Medium)Programming Live with Larry · 8:26 · 238 views
Number of Intersecting Interval Pairs II | LeetCode 520 Q2 | Sorting + Binary Search TrickGopo workspace · 8:23 · 190 views
Number of Intersecting Interval Pairs | LeetCode 4056 & 4057 | Weekly Contest 520 | Dry RunVIJAY KUMAR [IIT-BHU] · 22:28 · 96 views
LeetCode 4057 & 4056 | Number of Intersecting Interval Pairs I & II | C++Logic Mode · 24:46 · 66 views
The problem
You are given a 2D integer array intervals of n elements, where intervals[i] = [starti, endi] represents the closed interval from starti to endi.
Return the number of pairs of indices (i, j) such that 0 <= i < j < n and intervals[i] and intervals[j] intersect.
Two intervals intersect if they have at least one point in common, including when they only share an endpoint.
Example 1:
Input: intervals = [[1,2],[2,3],[3,4]]
Output: 2
Explanation:
There are 2 intersecting interval pairs:
- Intervals
[1, 2]and[2, 3]intersect at the point 2. - Intervals
[2, 3]and[3, 4]intersect at the point 3.
Example 2:
Input: intervals = [[1,5],[2,4],[3,6]]
Output: 3
Explanation:
There are 3 intersecting interval pairs:
- The intersection of
[1, 5]and[2, 4]is[2, 4]. - The intersection of
[1, 5]and[3, 6]is[3, 5]. - The intersection of
[2, 4]and[3, 6]is[3, 4].
Example 3:
Input: intervals = [[1,2],[3,4],[5,6]]
Output: 0
Explanation:
There are no intersecting interval pairs. Hence, the answer is 0.
Constraints:
2 <= n == intervals.length <= 105intervals[i] = [starti, endi]0 <= starti <= endi <= 109
Approach overview
Problem Overview: You get a list of intervals [l, r] and need to count the pairs of intervals that share at least one point. Count each unordered pair once.
Approach 1: Brute Force Pairwise Check (O(n^2) time, O(1) space)
Compare every pair (i, j) with i < j and test overlap with max(l_i, l_j) <= min(r_i, r_j). Increment a counter on each match. This is correct and quick to write, and it shows you understand the overlap condition. It is too slow once n reaches the upper constraint, so treat it as a starting point and a way to verify your optimized code on small inputs.
Approach 2: Sorting + Binary Search (O(n log n) time, O(n) space)
Count the complement instead. Two intervals fail to intersect exactly when one ends strictly before the other starts, and both cannot happen at once. So the number of disjoint pairs equals the number of ordered pairs where r_i < l_j. Sort all start values. For each interval, binary search the sorted starts to count how many start strictly after r_i. Sum those counts, then subtract from n(n-1)/2. The sort and binary search make each lookup logarithmic, which beats the quadratic scan.
Approach 3: Sorting + Two Pointers (O(n log n) time, O(n) space)
Sort the starts and the ends separately, then sweep both arrays with one pointer each. Advance the end pointer whenever the next end is smaller than the next start, and accumulate how many starts remain unmatched at each step. This replaces the per-element binary search with a single linear merge after sorting, so the sorting step is the only expensive part. Prefer this version in production code and interviews because it has the cleanest loop and the same asymptotic cost as Approach 2 with better constants.
Recommended for interviews: Start by describing the brute force so the interviewer sees you understand the overlap condition. Then move to the complement counting idea, which is the key insight. Implement the two pointer version with sorting and array manipulation. Mention binary search as the alternative. The brute force shows understanding, but the complement counting with two pointers shows skill.
Solution
Thinking
The statement matches the previous problem, but
n = 10^5, so enumerating every pair times out and the check must drop toO(n log n).The disjoint condition is unchanged. Subtracting the pairs where one interval ends before the other starts from the total yields the intersecting pairs.
Sorting plus two pointers is still enough. The number of pairs can reach
10^{10}, so we need 64-bit integers.
Two closed intervals [l_1, r_1] and [l_2, r_2] are disjoint if and only if r_1 < l_2 or r_2 < l_1.
The total number of pairs is \frac{n(n-1)}{2}. We count the disjoint pairs and subtract them from the total.
Sort all left endpoints and all right endpoints in ascending order. Enumerate each left endpoint s from left to right, and maintain a pointer i for the number of intervals with ends[i] < s. Those intervals are disjoint from the current one, so we subtract that count from the answer.
Each disjoint pair is counted exactly once: the interval with the smaller right endpoint is charged when we scan the other interval's left endpoint. The answer may exceed the 32-bit integer range, so we use 64-bit integers.
The time complexity is O(n times log n) and the space complexity is O(n), where n is the number of intervals.
class Solution:
def countIntersectingIntervals(self, intervals: list[list[int]]) -> int:
n = len(intervals)
starts = sorted(s for s, _ in intervals)
ends = sorted(e for _, e in intervals)
ans = n * (n - 1) // 2
i = 0
for start in starts:
while i < n and ends[i] < start:
i += 1
ans -= i
return ansclass Solution {
public long countIntersectingIntervals(int[][] intervals) {
int n = intervals.length;
int[] starts = new int[n];
int[] ends = new int[n];
for (int i = 0; i < n; i++) {
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
Arrays.sort(starts);
Arrays.sort(ends);
long ans = (long) n * (n - 1) / 2;
int i = 0;
for (int start : starts) {
while (i < n && ends[i] < start) {
i++;
}
ans -= i;
}
return ans;
}
}class Solution {
public:
long long countIntersectingIntervals(vector<vector<int>>& intervals) {
int n = intervals.size();
vector<int> starts(n), ends(n);
for (int i = 0; i < n; i++) {
starts[i] = intervals[i][0];
ends[i] = intervals[i][1];
}
sort(starts.begin(), starts.end());
sort(ends.begin(), ends.end());
long long ans = 1LL * n * (n - 1) / 2;
int i = 0;
for (int start : starts) {
while (i < n && ends[i] < start) {
i++;
}
ans -= i;
}
return ans;
}
};function countIntersectingIntervals(intervals: number[][]): number {
const n = intervals.length;
const starts = intervals.map(([s]) => s).sort((a, b) => a - b);
const ends = intervals.map(([, e]) => e).sort((a, b) => a - b);
let ans = (n * (n - 1)) / 2;
let i = 0;
for (const start of starts) {
while (i < n && ends[i] < start) {
i++;
}
ans -= i;
}
return ans;
}func countIntersectingIntervals(intervals [][]int) int64 {
n := len(intervals)
starts := make([]int, n)
ends := make([]int, n)
for i, p := range intervals {
starts[i] = p[0]
ends[i] = p[1]
}
slices.Sort(starts)
slices.Sort(ends)
ans := int64(n) * int64(n-1) / 2
i := 0
for _, start := range starts {
for i < n && ends[i] < start {
i++
}
ans -= int64(i)
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pairwise Check | O(n^2) | O(1) | Small inputs or verifying optimized code |
| Sorting + Binary Search | O(n log n) | O(n) | When you need a per-interval lookup |
| Sorting + Two Pointers | O(n log n) | O(n) | General case and interview default |
Frequently asked questions
Is Number of Intersecting Interval Pairs II easy or hard?
It is a medium difficulty problem with an acceptance rate around 50 percent. The brute force is easy to write, but the complement counting insight and the two pointer implementation are what make it a medium.
Number of Intersecting Interval Pairs II Python and Java solution?
The solution is the same in both languages. Sort the start and end arrays, use two pointers to count disjoint pairs, then return the total pair count minus the disjoint count. FleetCode provides full working code in Python, Java, C++, Go, and TypeScript.
How to solve Number of Intersecting Interval Pairs II in O(n log n)?
Sort the starts and ends separately. Count disjoint pairs where one interval ends strictly before another starts, using a two pointer sweep or binary search. Then subtract the disjoint count from the total number of pairs n(n-1)/2.
What is the best approach for Number of Intersecting Interval Pairs II?
The best approach is sorting plus two pointers. Count the non-intersecting pairs by sorting interval starts and ends, then sweep both arrays with one pointer each, and subtract that count from n(n-1)/2. This runs in O(n log n) time with O(n) extra space.
What data structure is used in Number of Intersecting Interval Pairs II?
The solution uses arrays, specifically two sorted arrays holding interval starts and ends. No hash map or tree is required. The main work is sorting plus a linear or binary search sweep over those arrays.
What is the time complexity of Number of Intersecting Interval Pairs II?
The optimal solution runs in O(n log n) time, dominated by sorting the interval endpoints. The brute force pairwise check runs in O(n^2) time and is only practical for small inputs.
Is Number of Intersecting Interval Pairs II asked at Google, Amazon, or Meta?
FleetCode does not have confirmed company frequency data for this problem in the tags used here. Check the problem page on FleetCode for current company tags before you prepare around a specific employer.