# Solution: Range Module

Let’s solve the Range Module problem using the Custom Data Structures pattern.

## We'll cover the following

## 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

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)$ to the ranges being tracked. If the interval overlaps with existing ranges, it should add only the numbers within$[left,~right)$ that are*not*already being tracked.**Query Range():**Returns true if every real number within the interval$[left,~right)$ is currently being tracked, and false otherwise.**Remove Range():**Removes tracking for every real number within the half-open interval$[left,~right)$ .

**Constraints:**

$1 \leq$ `left`

$<$ `right`

$\leq 10^4$ At most,

$10^3$ calls will be made to**Add Range(), Query Range(),**and**Remove Range().**

## Solution

Let’s look at the step-by-step implementation of the functions:

**Add Range(left, right):**This function adds a new interval`[left, right]`

to the list of intervals, merging it with any overlapping intervals.If the new interval is completely outside the existing intervals:

Append the new interval to the end if it is to the right of all existing intervals.

Insert the new interval at the beginning if it is to the left of all existing intervals.

If the new interval overlaps with existing intervals:

Find the overlapping intervals using the

`CheckIntervals`

method.Calculate the minimum start and maximum end of the overlapping intervals and the new interval to determine the new interval’s boundaries.

Replace the overlapping intervals with this newly merged interval to keep the list nonoverlapping.

**Remove Range(left, right):**This function removes a given interval`[left, right]`

from the list of intervals, splitting any overlapping intervals as needed.Do nothing if no intervals exist or the removal range is outside the existing intervals.

Find the overlapping intervals using the

`CheckIntervals`

method.For each overlapping interval:

If the interval starts before the removal range, create a new interval from the start to the beginning of the removal range.

If the interval ends after the removal range, create a new interval from the end of the removal range to the end of the interval.

Replace the overlapping intervals with the new ones excluding the removal range, keeping the list non-overlapping.

**Query Range(left, right)**: This function checks if any of the existing intervals fully cover a given interval`[left, right]`

.If there are no intervals, return FALSE.

Find the overlapping intervals using the

`CheckIntervals`

method.Verify the start and end boundaries to check if the range

`[left, right]`

is fully contained within one of the identified intervals.

**Check Intervals(left, right):**This helper function identifies the indexes of intervals that overlap or touch a given interval`[left, right]`

.Use a binary search-like approach with an initial mid-point

`mid`

that starts at half the array size.While

`mid`

is greater than or equal to$1$ Increment

`minRange`

by`mid`

if the end of the interval at`minRange + mid - 1`

is less than`left`

.Decrement

`maxRange`

by`mid`

if the start of the interval at`maxRange - mid + 1`

is greater than`right`

.Halve

`mid`

to refine the search area.

Return the indexes

`minRange`

and`maxRange`

that mark the boundaries of the overlapping intervals.

Let’s look at the following illustration to get a better understanding of the solution:

Level up your interview prep. Join Educative to access 80+ hands-on prep courses.