Tap here to switch tabs
Problem
Ask
Submissions

Problem: Range Module

hard
40 min
Explore how to design a Range Module data structure that efficiently manages half-open intervals. Learn to add, query, and remove numerical ranges while handling overlaps. This lesson helps you understand custom data structures for tracking ranges in coding interviews, preparing you to solve related problems with precision.

Statement

Design a Range Module data structure that effectively tracks ranges of numbers using half-open intervals and allows querying these ranges. A half-open interval [left,right)[left, right) includes all real numbers nn where leftn<rightleft\leq n <right.

Implement the RangeModule class with the following specifications:

  • Constructor(): Initializes a new instance of the data structure.

  • Add Range(): Adds the half-open interval [left, right)[left,~right) to the ranges being tracked. If the interval overlaps with existing ranges, it should add only the numbers within [left, right)[left,~right) that are not already being tracked.

  • Query Range(): Returns true if every real number within the interval [left, right)[left,~right) is currently being tracked, and false otherwise.

  • Remove Range(): Removes tracking for every real number within the half-open interval [left, right)[left,~right).

Constraints:

  • 11 \leq left << right 104\leq 10^4

  • At most, 10310^3 calls will be made to Add Range(), Query Range(), and Remove Range().

Tap here to switch tabs
Problem
Ask
Submissions

Problem: Range Module

hard
40 min
Explore how to design a Range Module data structure that efficiently manages half-open intervals. Learn to add, query, and remove numerical ranges while handling overlaps. This lesson helps you understand custom data structures for tracking ranges in coding interviews, preparing you to solve related problems with precision.

Statement

Design a Range Module data structure that effectively tracks ranges of numbers using half-open intervals and allows querying these ranges. A half-open interval [left,right)[left, right) includes all real numbers nn where leftn<rightleft\leq n <right.

Implement the RangeModule class with the following specifications:

  • Constructor(): Initializes a new instance of the data structure.

  • Add Range(): Adds the half-open interval [left, right)[left,~right) to the ranges being tracked. If the interval overlaps with existing ranges, it should add only the numbers within [left, right)[left,~right) that are not already being tracked.

  • Query Range(): Returns true if every real number within the interval [left, right)[left,~right) is currently being tracked, and false otherwise.

  • Remove Range(): Removes tracking for every real number within the half-open interval [left, right)[left,~right).

Constraints:

  • 11 \leq left << right 104\leq 10^4

  • At most, 10310^3 calls will be made to Add Range(), Query Range(), and Remove Range().