You are given a 2D integer array ranges where ranges[i] = [starti, endi] denotes that all integers between starti and endi (both inclusive) are contained in the ith range.
You are to split ranges into two (possibly empty) groups such that:
Two ranges are said to be overlapping if there exists at least one integer that is present in both ranges.
[1, 3] and [2, 5] are overlapping because 2 and 3 occur in both ranges.Return the total number of ways to split ranges into two groups. Since the answer may be very large, return it modulo 109 + 7.
Example 1:
Input: ranges = [[6,10],[5,15]] Output: 2 Explanation: The two ranges are overlapping, so they must be in the same group. Thus, there are two possible ways: - Put both the ranges together in group 1. - Put both the ranges together in group 2.
Example 2:
Input: ranges = [[1,3],[10,20],[2,5],[4,8]] Output: 4 Explanation: Ranges [1,3], and [2,5] are overlapping. So, they must be in the same group. Again, ranges [2,5] and [4,8] are also overlapping. So, they must also be in the same group. Thus, there are four possible ways to group them: - All the ranges in group 1. - All the ranges in group 2. - Ranges [1,3], [2,5], and [4,8] in group 1 and [10,20] in group 2. - Ranges [1,3], [2,5], and [4,8] in group 2 and [10,20] in group 1.
Constraints:
1 <= ranges.length <= 105ranges[i].length == 20 <= starti <= endi <= 109Problem Overview: You are given several numeric ranges. If two ranges overlap, they must belong to the same group. The task is to count how many different ways you can split the ranges into valid groups where overlapping ranges stay together. The key observation: every independent merged interval can either form its own group or merge with others in a binary choice pattern.
Approach 1: Sort and Merge Overlapping Intervals (O(n log n) time, O(1) extra space)
This approach treats the problem like classic interval merging. First sort the ranges by their start value using a sorting step. Then iterate through the array and merge overlapping intervals by tracking the current end boundary. Every time you encounter a range that starts after the current merged end, you discovered a new independent interval group. If there are k independent merged groups, each group can either be combined with others or kept separate in a binary choice pattern, giving 2^k valid ways (modulo 1e9+7). The algorithm performs a single linear scan after sorting, making it efficient and easy to implement.
Approach 2: Disjoint Set Union (Union-Find) Algorithm (O(n² · α(n)) time, O(n) space)
This method models ranges as nodes in a graph. If two ranges overlap, connect them using a union-find structure. Iterate through every pair of ranges and perform a union operation when intervals intersect. After processing all pairs, the number of connected components equals the number of independent groups. The final answer is again 2^components modulo 1e9+7. This approach highlights the graph perspective of the problem and uses the classic array-based DSU structure with path compression and union by rank.
Recommended for interviews: The sorting + merging approach is what most interviewers expect. It reduces the problem to a well-known interval pattern and achieves O(n log n) time with minimal space. DSU demonstrates understanding of connected components but is less efficient because it checks many pairwise overlaps.
This approach involves sorting the ranges based on their starting points. After sorting, we iterate through the sorted list, merging overlapping ranges. We count the number of disjoint groups of ranges – every such group is independent and can be assigned to two different groups.
In the code, ranges are sorted based on the start value. As we iterate through the ranges, each time we encounter a start value greater than the current end value, we know a new independent group of ranges has started. The number of such groups is counted and the result is computed as 2 raised to the power of the group count, modulo 10^9 + 7.
Time Complexity: O(n log n) due to sorting, where n is the number of intervals.
Space Complexity: O(1), aside from input storage.
This approach uses the Union-Find data structure to manage groups of overlapping intervals. We treat each range's start and end as part of a graph, unioning connected nodes. The number of separate union sets tells us how many independent range groups we have.
The union-find structure helps classify overlapping ranges efficiently by treating them as connected components. Each unique component is a set of interconnected nodes representing overlapping intervals. By counting different root nodes, we determine the number of independent range groups.
Python
Time Complexity: O(n log n) for sorting, O(n^2) in the worst case for potential full connections.
Space Complexity: O(n) for parent array.
| Approach | Complexity |
|---|---|
| Approach 1: Sort and Merge Overlapping Intervals | Time Complexity: O(n log n) due to sorting, where n is the number of intervals. |
| Approach 2: Disjoint Set Union (Union-Find) Algorithm | Time Complexity: O(n log n) for sorting, O(n^2) in the worst case for potential full connections. |
| Approach | Time | Space | When to Use |
|---|---|---|---|
| Sort and Merge Overlapping Intervals | O(n log n) | O(1) | Best general solution when intervals can be sorted and processed sequentially |
| Disjoint Set Union (Union-Find) | O(n² · α(n)) | O(n) | Useful when modeling overlaps as graph connectivity or practicing union-find patterns |
Count Ways to Group Overlapping Ranges || Merge Intervals || Leetcode-2580 • Aryan Mittal • 2,003 views views
Watch 9 more video solutions →Practice Count Ways to Group Overlapping Ranges with our built-in code editor and test cases.
Practice on FleetCodePractice this problem
Open in Editor