LeetCode 2580 - Count Ways to Group Overlapping Ranges

LeetCode Problem 2580

Difficulty: 🟡 Medium
Topics: Array, Sorting

Solution

Problem Understanding

The problem gives us a list of integer ranges, where each range represents all integers between start and end, inclusive. We must divide all ranges into exactly two groups. Either group may be empty.

The important restriction is that overlapping ranges cannot be separated. If two ranges share at least one common integer, they must belong to the same group. This rule also applies transitively. For example, if range A overlaps with range B, and range B overlaps with range C, then all three ranges must be placed into the same group, even if A and C do not directly overlap.

The task is to count how many valid ways exist to assign the ranges into two groups while respecting these overlap constraints.

The input size can be as large as 10^5 ranges, so the solution must be efficient. A naive pairwise graph construction or brute-force assignment would be too slow.

A key observation is that overlapping ranges naturally form connected components. Every range inside the same connected component must go into the same group. Once we identify how many independent connected components exist, each component has exactly two choices:

• Put the entire component into group 1
• Put the entire component into group 2

If there are k independent overlap components, then the total number of valid assignments is:

$2^k$

The answer must be returned modulo:

$10^9 + 7$

Several edge cases are important:

• A single range always produces exactly 2 valid groupings.
• Completely disjoint ranges each form separate components.
• Fully overlapping ranges all belong to one component.
• Touching intervals such as [1,2] and [2,3] are overlapping because the integer 2 exists in both ranges.
• Nested intervals such as [1,10] and [3,5] are also overlapping.

Because the coordinates can be as large as 10^9, we cannot use any coordinate compression grid or interval marking approach. The solution must rely on sorting and interval merging logic.

Approaches

Brute Force Approach

A brute-force solution would try every possible assignment of ranges into two groups. Since each range has two choices, there are:

$2^n$

possible assignments.

For every assignment, we would check whether all overlapping ranges ended up in the same group. This requires comparing pairs of ranges to determine overlap relationships.

Two ranges [a,b] and [c,d] overlap if:

$\max(a,c) \leq \min(b,d)$

Checking all pairs costs O(n^2), and doing this for every assignment leads to exponential complexity.

This approach is correct because it exhaustively checks every possible grouping, but it is completely impractical for n = 10^5.

Optimal Approach

The key insight is that overlapping ranges form connected components.

Suppose we sort all ranges by starting position. Then we can sweep from left to right and merge all overlapping intervals into one component.

For example:

[1,3], [2,5], [4,8]

All three belong to the same component because each interval overlaps with the next.

Once we identify the number of independent merged components, the problem becomes very simple:

• Every component must stay together
• Each component independently chooses group 1 or group 2

Therefore, if there are k merged components, the total number of valid assignments is:

$2^k$

We compute this value modulo 10^9 + 7.

The merging process only requires sorting plus one linear scan.

Approach	Time Complexity	Space Complexity	Notes
Brute Force	O(2^n * n^2)	O(1)	Tries every grouping and validates overlaps
Optimal	O(n log n)	O(1) excluding sort space	Sorts intervals and counts merged overlap components

Algorithm Walkthrough

1. Sort all ranges by their starting coordinate.

Sorting allows us to process intervals from left to right. Once sorted, overlapping intervals will appear consecutively. 2. Initialize variables to track the current merged component.

We maintain:

• current_end, the farthest ending position of the current component
• components, the number of disconnected overlap groups found so far

3. Start processing the sorted ranges one by one.

The first interval always begins a new component. 4. For each next interval, compare its start with current_end.

If:

$start \leq current_end$

then the interval overlaps with the current component.

We merge it by updating:

$current_end = \max(current_end, end)$ 5. If the interval does not overlap, start a new component.

This means:

$start > current_end$

Since there is no overlap, this interval belongs to a completely independent group of ranges.

Increment the component count. 6. After processing all ranges, compute the answer.

If there are components independent overlap groups, then the number of valid assignments is:

$2^{components} \bmod (10^9+7)$

Why it works

The algorithm works because overlapping intervals create connected components. Every interval inside the same connected component must be assigned together, otherwise at least one overlap constraint would be violated.

Sorting guarantees that all intervals belonging to the same component appear consecutively. The merge scan correctly identifies each maximal connected overlap group.

Since each component can independently choose one of two groups, multiplying two choices per component gives:

$2^k$

where k is the number of components.

Python Solution

from typing import List

class Solution:
    def countWays(self, ranges: List[List[int]]) -> int:
        MOD = 10**9 + 7

        ranges.sort()

        components = 0
        current_end = -1

        for start, end in ranges:
            if start > current_end:
                components += 1
                current_end = end
            else:
                current_end = max(current_end, end)

        return pow(2, components, MOD)

The implementation begins by sorting the intervals. Python's default list sorting sorts lexicographically, which means intervals are sorted first by start coordinate and then by end coordinate. This is exactly what we need.

The variable components tracks how many disconnected overlap groups exist.

The variable current_end stores the farthest right endpoint of the current merged component.

During iteration:

• If start > current_end, the current interval does not overlap with the previous component, so we start a new component.
• Otherwise, the interval overlaps, and we extend the merged boundary if necessary.

Finally, we compute:

$2^{components} \bmod (10^9+7)$

using Python's built-in modular exponentiation.

Go Solution

package main

import (
	"sort"
)

func countWays(ranges [][]int) int {
	const MOD int = 1_000_000_007

	sort.Slice(ranges, func(i, j int) bool {
		if ranges[i][0] == ranges[j][0] {
			return ranges[i][1] < ranges[j][1]
		}
		return ranges[i][0] < ranges[j][0]
	})

	components := 0
	currentEnd := -1

	for _, interval := range ranges {
		start, end := interval[0], interval[1]

		if start > currentEnd {
			components++
			currentEnd = end
		} else if end > currentEnd {
			currentEnd = end
		}
	}

	result := 1

	for i := 0; i < components; i++ {
		result = (result * 2) % MOD
	}

	return result
}

The Go implementation follows the same logic as the Python version.

Since Go does not provide built-in modular exponentiation for integers in the standard style used by Python's pow, we compute powers of 2 iteratively.

The sorting step uses sort.Slice with a custom comparator.

The rest of the algorithm uses integer variables and a simple linear scan through the intervals.

Worked Examples

Example 1

ranges = [[6,10],[5,15]]

Step 1: Sort the intervals

Sorted Intervals
[5,15]
[6,10]

Step 2: Process intervals

Interval	current_end Before	Overlaps?	components	current_end After
[5,15]	-1	No	1	15
[6,10]	15	Yes	1	15

We found exactly 1 connected component.

Number of ways:

$2^1 = 2$

Final answer:

2

Example 2

ranges = [[1,3],[10,20],[2,5],[4,8]]

Step 1: Sort the intervals

Sorted Intervals
[1,3]
[2,5]
[4,8]
[10,20]

Step 2: Process intervals

Interval	current_end Before	Overlaps?	components	current_end After
[1,3]	-1	No	1	3
[2,5]	3	Yes	1	5
[4,8]	5	Yes	1	8
[10,20]	8	No	2	20

We found 2 disconnected components:

• Component 1: [1,3], [2,5], [4,8]
• Component 2: [10,20]

Number of ways:

$2^2 = 4$

Final answer:

4

Complexity Analysis

Measure	Complexity	Explanation
Time	O(n log n)	Sorting dominates the runtime
Space	O(1) excluding sort space	Only a few variables are used

The linear scan after sorting takes O(n) time. The expensive step is sorting the intervals, which costs O(n log n).

No auxiliary data structures proportional to input size are required. Aside from sorting internals, the algorithm only uses a few integer variables.

Test Cases

from typing import List

class Solution:
    def countWays(self, ranges: List[List[int]]) -> int:
        MOD = 10**9 + 7

        ranges.sort()

        components = 0
        current_end = -1

        for start, end in ranges:
            if start > current_end:
                components += 1
                current_end = end
            else:
                current_end = max(current_end, end)

        return pow(2, components, MOD)

sol = Solution()

assert sol.countWays([[6,10],[5,15]]) == 2
# Single overlap component

assert sol.countWays([[1,3],[10,20],[2,5],[4,8]]) == 4
# Two disconnected components

assert sol.countWays([[1,2]]) == 2
# Single interval

assert sol.countWays([[1,2],[3,4],[5,6]]) == 8
# No overlaps, 3 independent components

assert sol.countWays([[1,10],[2,3],[4,5],[6,7]]) == 2
# Fully nested overlaps

assert sol.countWays([[1,2],[2,3],[3,4]]) == 2
# Boundary touching counts as overlap

assert sol.countWays([[1,5],[6,10],[11,15],[5,6]]) == 2
# Transitive overlap merges everything

assert sol.countWays([[0,0],[1,1],[2,2],[3,3]]) == 16
# Completely disjoint singleton ranges

assert sol.countWays([[1,1000000000],[2,999999999]]) == 2
# Large coordinate values

assert sol.countWays([[1,4],[2,3],[10,20],[15,25],[30,40]]) == 8
# Three separate components

Test	Why
[[6,10],[5,15]]	Basic overlap case
[[1,3],[10,20],[2,5],[4,8]]	Multiple connected components
[[1,2]]	Smallest valid input
[[1,2],[3,4],[5,6]]	Completely independent ranges
[[1,10],[2,3],[4,5],[6,7]]	Nested intervals
[[1,2],[2,3],[3,4]]	Endpoint overlap handling
[[1,5],[6,10],[11,15],[5,6]]	Transitive merging
[[0,0],[1,1],[2,2],[3,3]]	Multiple singleton components
[[1,1000000000],[2,999999999]]	Large coordinate values
[[1,4],[2,3],[10,20],[15,25],[30,40]]	Several independent groups

Edge Cases

One important edge case occurs when intervals only touch at boundaries. For example, [1,2] and [2,3] overlap because both contain the integer 2. A common mistake is using a strict inequality such as start >= current_end, which would incorrectly separate touching intervals. The implementation correctly uses start > current_end to determine non-overlap.

Another important case is transitive overlap chains. Consider:

[1,3], [3,5], [5,7]

Even if the first and third intervals do not directly overlap much, all three belong to one connected component through chaining. The merge process naturally handles this because current_end continuously expands as overlapping intervals are processed.

Nested intervals are also easy to mishandle. For example:

[1,100], [20,30], [40,50]

A naive algorithm might incorrectly split the smaller intervals into separate groups. The current implementation keeps track of the maximum endpoint in the merged component, ensuring all nested intervals remain connected.

Finally, completely disjoint intervals produce the maximum number of groupings. If no intervals overlap, every interval forms its own component, leading to:

$2^n$

possible assignments. The implementation handles this efficiently with a single pass after sorting.