Abstract / Summary

Check if every number in a given range is included in a list of sorted intervals.

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 51% (100k+ submissions).

Typical patterns to solve this problem:

• Array
• Hash Table
• Prefix Sum

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 provided implementation determines whether every integer in the inclusive interval [left, right] is covered by at least one of the sub-intervals supplied in ranges. It does this by constructing a collection of the required numbers, then iteratively removing any number that appears in a given range. The final result is a Boolean indicating whether the collection is empty, which means all required numbers have been covered.

Core Logic

Initializing the set of required values

need = set(range(left, right + 1))

A set named need is created from a range object that enumerates every integer from left through right. The use of a set provides constant-time membership tests and deletions, which is essential for the subsequent removal phase.

Traversing the input ranges

for l, r in ranges:
    for i in range(l, r + 1):
        need.discard(i)

The outer loop extracts the lower and upper bounds of each sub-interval. The inner loop iterates over every integer inside the current interval, invoking discard on the need set. discard removes the element if it exists and does nothing otherwise, which gracefully handles numbers that are either already removed or lie outside the target interval.

Determining the final outcome

return not need

The expression not need evaluates to True when the set is empty, indicating that all required numbers have been removed and therefore covered. If any element remains, the result is False.

Edge Cases Handled

When left exceeds right, the range(left, right + 1) expression yields an empty sequence, resulting in an empty need set. The subsequent loops have no effect, and the function returns True, correctly indicating that there is nothing to cover.

If ranges contains intervals that are completely outside the [left, right] window, the inner loop still iterates over those numbers, but discard simply ignores them because they are not present in need. This avoids unnecessary conditional checks.

Overlapping or duplicate intervals are also accommodated. Since need is a set, each required number is stored only once, and repeated discard calls on the same element have no adverse effect.

When ranges is an empty list, the outer loop never executes. The function then returns True only if the initial need set is empty (i.e., when left > right). Otherwise, it returns False, correctly reflecting that no numbers are covered.

Performance Optimizations Observed

The algorithm leverages the set data structure to achieve constant-time removal of elements. By using discard instead of remove, it avoids the overhead of exception handling for missing elements, which would occur if remove were used on numbers not present in need.

Creating the need set from a range object is efficient because the range is lazily generated and the conversion to a set occurs in a single pass. This avoids the need for multiple scans of the target interval.

The nested loops directly iterate over the numeric values of each interval rather than performing repeated containment checks against the original list of ranges. This reduces the number of comparisons required to determine coverage.

Overall, the design focuses on minimizing per-element work by using data structures that provide fast membership operations and by eliminating unnecessary conditional branches.

Imagine you have a long, colorful line made of numbered blocks. Some of the blocks are sitting in a row, and you want to make sure every single block from the number left all the way to the number right is covered by a special blanket.

First, think of a big collection that holds all the numbers between left and right that need to be covered. You gather these numbers into a group.

Next, you look at each blanket in the list one by one. Each blanket has a starting number and an ending number. You look at every number covered by that blanket. If you see a number that is currently in the group of ones you still need, you take it out of that group. It is like crossing off a number on a checklist once you know a blanket is covering it.

After checking every single blanket, you look at the group again. If the group has become completely empty, it means every number was covered, and there is nothing left to worry about.

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

not analyzed yet

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++	JS	Java		Python			Go	TS
	Progiez	C++		Java		Python
github	black-shadows	C++
	charles-wangkai			Java
	DimitrisJim							C
	everthis		JS
	fartem				Ruby
	fsq	C++
	JoshCrozier		JS
	lkwq007					Python
	suxrobGM						C#
	varunu28			Java
	wisdompeak	C++
AlgoMonster	C++, Python, Java, TypeScript
WalkCCC	C++, Python, Java
leetcode.ca	C++, Go, Java, JavaScript, Python, TypeScript
Progiez	C++, Java, Python
black-shadows	C++, C++
charles-wangkai	Java
DimitrisJim	C
everthis	JavaScript
fartem	Ruby
fsq	C++
JoshCrozier	JavaScript
lkwq007	Python
suxrobGM	C#
varunu28	Java
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