Skip to main content
Talentd

Count Ways to Group Overlapping Ranges - Solution & Explanation

MediumArraySorting12 min readAsked at: Oracle, IBM
Practice this problem

Problem Statement

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:

  • Each range belongs to exactly one group.
  • Any two overlapping ranges must belong to the same group.

Two ranges are said to be overlapping if there exists at least one integer that is present in both ranges.

  • For example, [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 <= 105
  • ranges[i].length == 2
  • 0 <= starti <= endi <= 109

Approach Overview

Problem 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.

Approach 1: Approach 1: Sort and Merge Overlapping Intervals

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.

Code

PythonJava

Python

Java

Complexity

Time Complexity: O(n log n) due to sorting, where n is the number of intervals.
Space Complexity: O(1), aside from input storage.

Try this approach in the editor ā†’

Approach 2: Approach 2: Disjoint Set Union (Union-Find) Algorithm

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.

Code

Python

Python

Complexity

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.

Try this approach in the editor ā†’

Approach 3: Sorting + Counting + Fast Power

We can first sort the intervals in the range, merge the overlapping intervals, and count the number of non-overlapping intervals, denoted as cnt.

Each non-overlapping interval can be chosen to be put in the first group or the second group, so the number of plans is 2^{cnt}. Note that 2^{cnt} may be very large, so we need to take modulo 10^9 + 7. Here, we can use fast power to solve this problem.

The time complexity is O(n times log n), and the space complexity is O(log n). Here, n is the number of intervals.

Alternatively, we can also avoid using fast power. Once a new non-overlapping interval is found, we multiply the number of plans by 2 and take modulo 10^9 + 7.

Code

PythonJavaC++GoTypeScript

Python

Java

C++

Go

TypeScript

Try this approach in the editor ā†’

Approach 4: Default Approach

Code

PythonJavaC++Go

Python

Java

C++

Go

Try this approach in the editor ā†’

Complexity Comparison

ApproachComplexity
Approach 1: Sort and Merge Overlapping Intervals

Time Complexity: O(n log n) due to sorting, where n is the number of intervals.
Space Complexity: O(1), aside from input storage.

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.
Space Complexity: O(n) for parent array.

Sorting + Counting + Fast Powerā€”
Default Approachā€”

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
Sort and Merge Overlapping IntervalsO(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

Video Solution

Count Ways to Group Overlapping Ranges || Merge Intervals || Leetcode-2580 ā€¢ Aryan Mittal ā€¢ 2,042 views views

Watch 9 more video solutions ā†’

Frequently Asked Questions

Is Count Ways to Group Overlapping Ranges easy or hard?
This problem is rated Medium on LeetCode. The difficulty comes from recognizing that overlapping ranges form connected groups and that the final answer depends on counting those groups and computing powers of two.
Count Ways to Group Overlapping Ranges Python/Java solution
Typical implementations sort the ranges and iterate once to merge overlaps. Python and Java solutions both compute the number of merged groups and then calculate 2^k modulo 1e9+7 using fast exponentiation or built-in power functions.
How to solve Count Ways to Group Overlapping Ranges in O(n)?
A pure O(n) solution is generally not possible because the ranges must be ordered to detect overlaps reliably. Sorting introduces an O(n log n) step. After sorting, the merging phase itself runs in O(n) time while counting independent groups.
What is the best approach for Count Ways to Group Overlapping Ranges?
The most efficient approach sorts the ranges and merges overlapping intervals. After sorting, you scan the array and count how many independent merged groups exist. If there are k groups, the number of valid ways to group them is 2^k modulo 1e9+7. This method runs in O(n log n) time and O(1) extra space.
Is Count Ways to Group Overlapping Ranges asked at Google/Amazon/Meta?
Interval merging and grouping problems frequently appear in interviews at companies like Google, Amazon, and Meta. This problem specifically tests sorting, interval processing, and recognizing independent components, which are common patterns in system and algorithm interviews.
What data structure is used in Count Ways to Group Overlapping Ranges?
The most common solution uses arrays with sorting and a running interval boundary. An alternative approach uses the Union-Find (Disjoint Set Union) data structure to connect overlapping ranges and count connected components.
What is the time complexity of Count Ways to Group Overlapping Ranges?
The optimal solution runs in O(n log n) time because the ranges must be sorted before merging. After sorting, a single linear scan processes overlaps. Space complexity is O(1) if the merge is performed in place, excluding the input array.

Ready to solve this problem?

Practice Count Ways to Group Overlapping Ranges with our built-in code editor and test cases.

Practice on FleetCode
Previous

Merge Intervals