Count Ways to Group Overlapping Ranges — Medium Problem & Solution

Problem statement

ranges[i] = [start, end] is an inclusive range of integers. Split all the ranges into two groups so that any two ranges sharing at least one integer end up in the same group. Either group may be empty.

Return the number of ways to do this, modulo 10⁹ + 7. Two ways differ if some range lands in a different group.

Example 1

Input: ranges = [[6,10],[5,15]]
Output: 2
Explanation: They overlap, so both go together — into group 1 or group 2.

Example 2

Input: ranges = [[1,3],[10,20],[2,5],[4,8]]
Output: 4
Explanation: `[1,3]`, `[2,5]` and `[4,8]` merge into one block; `[10,20]` is its own. 2² = 4.

Example 3

Input: ranges = [[1,2]]
Output: 2

Constraints

• 1 <= ranges.length <= 10^5
• ranges[i].length == 2
• 0 <= starti <= endi <= 10^9

How to solve Count Ways to Group Overlapping Ranges

Sort by start and sweep, merging ranges into maximal blocks: a range starts a new block only when its start is beyond the furthest end reached so far. Each block is then independent, so the answer is 2^blocks.

Approach

1. Sort the ranges by start.
2. Track reach, the furthest end covered. A range with start > reach opens a new block.
3. Extend reach to the range's end when it goes further.
4. Return 2^blocks modulo 10⁹ + 7.

Why it works

"Share an integer" is transitive once the ranges are merged — a chain of pairwise overlaps forms a single connected block, which is why a union-find solution and this sweep give the same count. Sorting by start is what lets one reach variable stand in for the whole block: any later range that starts at or before reach must touch something already inside it.

Complexity

• Time — O(n log n)
• Space — O(n)

Pitfalls

• Touching endpoints count as overlapping: [1,3] and [3,5] share the integer 3.
• reach must be the maximum end so far, not the previous range's end — a nested range would otherwise close the block early.
• The exponent is the number of blocks, not the number of ranges.

Reference solution

Python

from typing import List

def countWays(ranges: List[List[int]]) -> int:
    MOD = 10**9 + 7
    groups = 0
    reach = -1
    for start, end in sorted(ranges):
        if start > reach:
            groups += 1
        reach = max(reach, end)
    return pow(2, groups, MOD)

JavaScript

var countWays = function(ranges) {
    var MOD = 1000000007;
    var sorted = ranges.slice();
    sorted.sort(function(a, b) { return a[0] - b[0]; });
    var groups = 0, reach = -1;
    for (var i = 0; i < sorted.length; i++) {
        if (sorted[i][0] > reach) groups++;
        if (sorted[i][1] > reach) reach = sorted[i][1];
    }
    var answer = 1;
    for (var g = 0; g < groups; g++) answer = (answer * 2) % MOD;
    return answer;
};

Also on the editorial tab: C, C#, C++, Go, Java, Kotlin, PHP, Ruby, Rust, Swift, TypeScript.

More arrays problems

• Minimum Number of Increments on Subarrays to Form a Target Array Medium
• Find the Winner of an Array Game Medium
• Queries on a Permutation With Key Medium
• Corporate Flight Bookings Medium
• Find the Winner of the Circular Game Medium
• Longest Subsequence With Limited Sum Medium