Solution: Range Module

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

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().

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 check_intervals 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 check_intervals 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 check_intervals 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 list size.

    • While mid is greater than or equal to 11

      • Increment min_range by mid if the end of the interval at min_range + mid - 1 is less than left.

      • Decrement max_range by mid if the start of the interval at max_range - mid + 1 is greater than right.

      • Halve mid to refine the search area.

    • Return the indexes min_range and max_range 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.