Abstract / Summary

Count the number of ways to group ranges so that any overlapping ranges are in the same group.

Note

The full problem description, including helpful examples, can be found on LeetCode.

This problem is ranked as

and has an acceptance rate of about 38% (50k+ submissions).

Typical patterns to solve this problem:

• Array
• Sorting

Every single line of code was written by me, 100% from scratch, between August 2023 and August 2024.
However, two years later I set up this website and used various AI tools to generate most of the walkthrough / explanations below.

See this dedicated page for more details.

Overview

The countWays method receives a collection of integer intervals and determines how many independent groups of overlapping intervals exist. Each group can be either selected or omitted, leading to a total of (2^{\text{groups}}) possible selections. The result is returned modulo (1{,}000{,}000{,}007).

Key Steps

Building the difference map

delta = defaultdict(int)
for a, b in ranges:
    delta[a] += 1
    delta[b] -= 1

A dictionary named delta records the net change in the number of active intervals at each endpoint. Adding +1 at the start point and -1 at the end point creates a compact representation that can later be swept to reconstruct the overlap count.

Sweeping through sorted positions

distinct = 0
overlap  = 0
for pos, change in sorted(delta.items()):
    overlap += change
    if overlap == 0:
        distinct += 1

The keys of delta are sorted, producing a chronological scan of all interval boundaries. The variable overlap tracks how many intervals are currently open. Whenever overlap drops to zero, the scan has just closed a contiguous block of overlapping intervals, so distinct is incremented to reflect the discovery of a new independent group.

Computing the final result

return pow(2, distinct, 1_000_000_007)

The built-in pow function raises 2 to the power of distinct while applying the required modulus, delivering the count of selectable configurations.

Edge Cases Handled

When the input list is empty, the delta map remains empty, the sweep loop never executes, and distinct stays at 0. Consequently the function returns pow(2, 0, MOD), which equals 1, representing the single way to choose nothing.

If a single interval is supplied, the map contains a +1 at its start and a -1 at its end. The sweep sees the overlap rise to 1 and then fall to 0, causing distinct to become 1, and the result is 2, reflecting the choice to include or exclude that interval.

Intervals that share an endpoint, such as [1,3] and [3,5], generate a +1 and a -1 at the same coordinate. The net change at that point correctly balances, ensuring that the overlap count does not artificially dip below zero and that the two intervals are treated as part of the same group when they touch.

Fully nested intervals, for example [2,8] containing [4,6], produce multiple +1 entries before any -1 appears. The overlap counter climbs to 2 and only returns to 0 after the outer interval ends, so the nested structure is recognized as a single group.

Adjacent intervals that do not overlap, like [1,2] and [3,4], generate separate regions where the overlap count reaches zero between them. The sweep therefore increments distinct twice, counting each interval as its own independent group.

Performance Optimizations

The algorithm avoids constructing an explicit list of all interval points; instead it aggregates changes in a dictionary, which reduces memory usage when many intervals share endpoints. Sorting only the unique keys of delta limits the work to the number of distinct endpoints rather than the total number of interval boundaries.

Using Python’s defaultdict eliminates the need for explicit existence checks before updating counts, streamlining the construction of the difference map.

The final exponentiation leverages the three-argument form of pow, which implements fast modular exponentiation internally, ensuring that even large values of distinct are processed efficiently.

Imagine a long playground with many colorful ribbons spread out on the grass. Some ribbons overlap, covering the same spots, while others are all by themselves. Finding out how many separate groups of ribbons exist is like solving a treasure hunt.

The code starts by looking at where each ribbon begins and where it ends. It creates a list of tiny markers for every start and stop point. Think of these markers as little flags placed on the ground to show where the ribbons start appearing and where they finally vanish.

Next, the code goes on a walk across the playground, starting from the very first flag. It keeps track of how many ribbons are stacked up at any moment by watching the flags go up and down. When the number of ribbons being held in the air drops all the way to zero, that means the current group of ribbons has finished completely. This is the moment to count one whole, separate collection.

Once all the groups are counted, the code figures out the total number of ways to pick and choose from those groups. It does this by multiplying the number two by itself for every group found. This leads to the final secret number that tells how many different combinations are possible.

Several LLMs ranked my code quality on a scale from 1 (very poor) to 10 (outstanding):

Time: loglinear
As a rule of thumb, the maximum input size for one second execution time is

• factorial: up to 10 elements
• exponential: up to 20 elements
• polynomial: a few thousand elements
• loglinear: up to 100,000 elements
• linear: a few million elements
• logarithmic: a billion elements
• constant: practically unlimited

I wrote a basic crawler to find other solutions to that problem.
Obviously, I did that after I solved the problem myself.

In general, AlgoMonster and WalkCCC solutions are high-quality and always worth a look.
I haven't checked most of the other solutions, but they might be helpful as well.

And of course, the LeetCode forum is always a good place (or even the best) to look for alternative approaches.

(click on a column header to sort the table)

	author
author	solutions
www	AlgoMonster	C++		Java		Python	TS
	WalkCCC	C++		Java		Python
	leetcode.ca	C++		Java	Go	Python	TS
	Progiez	C++		Java		Python
github	charles-wangkai			Java
	everthis		JS
	fsq	C++
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, Python, TypeScript
Progiez	C++, Java, Python
charles-wangkai	Java
everthis	JavaScript
fsq	C++
wisdompeak	C++

There are a few extra pages giving you some insights into my setup:

• Tech Stack - my development environment and tools
• AI - how AI helped me create this website (NOT solving the problems)
• Progress - progression over time
• Quality - code quality