Number of Intersecting Interval Pairs I solution and explanation
9 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 · 330 views
4057. Number of Intersecting Interval Pairs II (Leetcode Medium)Programming Live with Larry · 8:26 · 233 views
Number of Intersecting Interval Pairs II | LeetCode 520 Q2 | Sorting + Binary Search TrickGopo workspace · 8:23 · 190 views
4056. Number of Intersecting Interval Pairs I (Leetcode Easy)Programming Live with Larry · 3:20 · 183 views
LeetCode Weekly Contest 520 Q1 | Number of Intersecting Interval Pairs I | Brute Force + O(n log n)Gopo workspace · 5:10 · 155 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 · 60 views
LeetCode 4056 Solution | Number of Intersecting Interval Pairs I | Weekly Contest 520 | C++Plum Codes · 6:13
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 <= 100intervals[i] = [starti, endi]0 <= starti <= endi <= 100
Approach overview
Problem Overview: You get a set of closed intervals [l, r]. Count the unordered pairs of intervals that share at least one point. Two intervals intersect when the larger start is less than or equal to the smaller end.
Approach 1: Brute Force Pair Check (O(n^2) time, O(1) space)
Use two nested loops to visit every pair (i, j) with i < j. For each pair, check whether max(l_i, l_j) <= min(r_i, r_j). If it holds, increment the counter. This is correct and easy to verify, but with n up to the constraint limit it does roughly n*(n-1)/2 comparisons. Use it to confirm your understanding of the intersection condition before optimizing.
Approach 2: Count Disjoint Pairs with Sorting and Two Pointers (O(n log n) time, O(n) space)
Counting intersecting pairs directly is awkward. Count the disjoint pairs instead and subtract from the total. Two intervals are disjoint exactly when one ends strictly before the other starts. For any disjoint pair, exactly one ordering satisfies r_i < l_j, so each disjoint pair is counted once. Copy the starts into an array L and the ends into an array R, then sort both. For each start l in L, advance a pointer over R while R[p] < l. The pointer value is the number of intervals that end before l begins. Sum these counts to get the disjoint total. The answer is n*(n-1)/2 minus that sum. Because both arrays are sorted and the pointers only move forward, the scan is linear after sorting.
Approach 3: Sorting with Binary Search (O(n log n) time, O(n) space)
This is the same counting idea as Approach 2, with the inner pointer replaced by a binary search. For each start l, run a lower-bound search on sorted R to find how many ends are strictly less than l. It costs O(log n) per query instead of an amortized O(1) pointer step. Use it when you prefer a direct formulation or want a clear reduction to binary search patterns. Both versions have the same overall complexity because sorting dominates.
Recommended for interviews: Start with the brute force pair check to show you understand the overlap condition. Then move to the sorting plus two pointers solution to show you can convert a pairwise problem into a counting problem over sorted arrays. The brute force shows understanding, but recognizing that disjoint pairs are easier to count than intersecting pairs shows skill. Work through the single-pass array logic carefully, since off-by-one errors on strict versus non-strict comparisons are the most common failure point.
Solution
Thinking
n \le 100, so enumerating every index pair and checking intersection would pass. Two closed intervals are disjoint if and only if one right endpoint is strictly less than the other left endpoint.Pairwise checks need both sides of that test. It is cleaner to start from
\frac{n(n-1)}{2}and subtract the disjoint pairs: for each left endpoint, count how many intervals have already ended before it starts.After sorting the left and right endpoints separately, a pointer that only moves right counts those finished intervals in one scan.
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 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 int 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);
int ans = 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:
int 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());
int ans = 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) int {
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 := n * (n - 1) / 2
i := 0
for _, start := range starts {
for i < n && ends[i] < start {
i++
}
ans -= i
}
return ans
}Complexity analysis
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Brute Force Pair Check | O(n^2) | O(1) | Small inputs or verifying the intersection condition |
| Sorting + Two Pointers | O(n log n) | O(n) | General case, preferred for interviews and large inputs |
| Sorting + Binary Search | O(n log n) | O(n) | When you want a direct per-element lookup formulation |
Frequently asked questions
Is Number of Intersecting Interval Pairs I easy or hard?
It is rated Easy with a 61.2 percent acceptance rate. The brute force idea is immediate, but the counting trick of subtracting disjoint pairs from the total is what separates a fast solution from a slow one. Most candidates solve it in under 30 minutes once they see that trick.
Number of Intersecting Interval Pairs I Python and Java solution?
In Python, sort the starts and ends, then use a while loop with an index into the sorted ends for each start, and subtract the disjoint count from n*(n-1)//2. In Java, use Arrays.sort on two int arrays and a single pointer loop, storing the total in a long to avoid overflow for large n. FleetCode provides both implementations on the solution page.
How to solve Number of Intersecting Interval Pairs I in O(n log n)?
Build arrays of all starts and all ends, and sort both. Total the number of pairs as n*(n-1)/2. For each start, advance a pointer over the sorted ends while the end is strictly less than that start, and add the pointer position to a disjoint count. Subtract the disjoint count from the total to get the number of intersecting pairs.
What is the best approach for Number of Intersecting Interval Pairs I?
The best approach is to count disjoint pairs instead of intersecting pairs, then subtract from the total. Sort the start values and end values separately and use two pointers to count how many intervals end before each start. This runs in O(n log n) time with O(n) extra space.
What data structure is used in Number of Intersecting Interval Pairs I?
The solution uses plain arrays. You store the interval start and end values in two arrays, sort them, and scan them with pointers or binary search. No hash map or tree structure is required.
What is the time complexity of Number of Intersecting Interval Pairs I?
The optimal solution runs in O(n log n) time because sorting the start and end arrays dominates the cost. The two-pointer scan after sorting is O(n). The brute force pair check runs in O(n^2) time.
Is Number of Intersecting Interval Pairs I asked at Google, Amazon, or Meta?
This problem is not confirmed by our tags as asked at a specific company. Its tags are Array, Binary Search, Sorting, and Enumeration, which match common interval and sorting interview questions. Practice it to build the sorting and counting pattern used in many interval problems.