Range Module LeetCode

In the Range Module problem, we are given a set of half-open intervals represented as [start, end). We must implement a data structure that can add, query, and remove intervals while keeping track of the disjoint intervals.

For example, calendar applications often represent events as time intervals. This problem can be applied to efficiently manage and query availability or schedule conflicts. In this Answer, we’ll explore this problem and provide a Python solution.

Problem statement

This problem includes three functions to keep track of a range of numbers. Here are a few rules about this problem:

The ranges will be provided as half-open intervals. These will be denoted as [left, right), where the left value is inclusive, and the right value is exclusive.
A half-open interval is defined as an interval that contains all real numbers, where left <= real numbers < right.
There are three methods to implement in this problem:
- addRange(left, right): Appends the half-open interval to the tracked intervals. If there’s an overlap in the intervals, we append any numbers in the interval that haven’t previously been tracked.
- queryRange(left, right): Returns True if the real numbers in the provided interval are being tracked, and False if not.
- removeRange(left, right): Stops tracking the real numbers being tracked in the half-open interval.

Algorithm

The algorithms for each function are provided below:

addRange():
- Initialize an empty list range to store the set of intervals.
- Iterate through the existing tracked intervals until reaching the interval before the new interval begins.
- Merge overlapping intervals by adjusting the left and right values.
- Append the merged interval to the list.
- Append the remaining intervals after the added interval.
- Update the value of __modules (tracked intervals).
queryRange():
- Use binary search from the bisect module to find the index where we should insert left.
- Check if the index covers the range. Return True if so.
The removeRange(left, right) Method:
- Initialize ranges.
- Iterate through the tracked intervals until reaching the interval before the target interval.
- If there’s an overlap, split the overlapping intervals into two segments. Delete the segments that are not required.
- Append the remaining intervals after the removed interval.
- Update the value of __modules (tracked intervals).

Educative 99 helps you solve complex coding problems like the range module problem by recognizing patterns and applying the right algorithms.

Knowledge test

Now that we have understood the problem, let’s test our understanding below:

import bisect
class RangeModule(object):
    def __init__(self):
        self.__modules = []
    def addRange(self, left, right):
        ranges = []
        i = 0
        while i < len(self.__modules) and self.__modules[i][1] <= left:
            ranges.append(self.__modules[i])
            i += 1
        while i < len(self.__modules) and self.__modules[i][0] < right:
            left = min(left, self.__modules[i][0])
            right = max(right, self.__modules[i][1])
            i += 1
        ranges.append((left, right))
        while i < len(self.__modules):
            ranges.append(self.__modules[i])
            i += 1
        self.__modules = ranges
    def queryRange(self, left, right):
        i = bisect.bisect_left(self.__modules, (left, float("inf")))
        if i > 0 and self.__modules[i - 1][1] >= right:
            return True
        return False
    def removeRange(self, left, right):
        ranges = []
        i = 0
        while i < len(self.__modules) and self.__modules[i][1] <= left:
            ranges.append(self.__modules[i])
            i += 1
        while i < len(self.__modules) and self.__modules[i][0] < right:
            if self.__modules[i][0] < left:
                ranges.append((self.__modules[i][0], left))
            if self.__modules[i][1] > right:
                ranges.append((right, self.__modules[i][1]))
            i += 1
        while i < len(self.__modules):
            ranges.append(self.__modules[i])
            i += 1
        self.__modules = ranges
def main():
    temp = RangeModule()
    temp.addRange(10, 20)
    temp.removeRange(14, 16)
    print(temp.queryRange(10, 14))
    print(temp.queryRange(13, 15))
    print(temp.queryRange(16, 17))
if __name__ == "__main__":
    main()

This code can be explained below:

Line 1: Import bisect, which we use to binary search on intervals.
Line 2: Define the RangeModule class.
Lines 5–6: Initialize the empty list ranges to store the intervals we’ve tracked.
Lines 8–27: Definition of the addRange method, which takes the variables left and right as parameters.
- Line 9: Initialize the empty list ranges, that stores the intervals.
- Lines 12–14: Iterate through the tracked intervals until we reach the one before the new interval begins.
- Lines 16–19: Merge the overlapping intervals by changing the left and right values.
- Line 21: Append the merged interval to ranges.
- Lines 23–25: Append the remaining intervals after the added interval.
- Line 27: Update the value of modules.
Lines 29–33: The queryRange method, which also takes left and right as parameters.
- Line 30: Use binary search from the bisect module to find the index where we should insert left.
- Line 31: Check if the index we found covers the range of the query.
Lines 35–54: Definition of the removeRange method, which takes the variables left and right as parameters. This method is similar to addRange, except that it splits the overlapping intervals into two segments. It then deletes the segments that aren’t required.
Lines 56–66: Our main to call our methods.

We may alter the main to test this code with our test cases.

Time and space complexity

The table below shows the time and space complexity from each function:

New on Educative

Learn to Code

Learn any Language as a beginner

Develop a human edge in an AI powered world and learn to code with AI from our beginner friendly catalog

🏆 Leaderboard

Daily Coding Challenge

Solve a new coding challenge every day and climb the leaderboard

Free Resources

Function	Time Complexity	Space Complexity
`addRange`	O(n)	O(n)
`queryRange`	O(log n)	O(1)
`removeRange`	O(n)	O(n)