Last updated on January 19th, 2025 at 02:47 am
Here, we see a Range Module LeetCode Solution. This Leetcode problem is solved using different approaches in many programming languages, such as C++, Java, JavaScript, Python, etc.
List of all LeetCode Solution
Topics
Ordered Map, Segment Tree
Level of Question
Hard
Range Module LeetCode Solution
Table of Contents
1. Problem Statement
A Range Module is a module that tracks ranges of numbers. Design a data structure to track the ranges represented as half-open intervals and query about them.
A half-open interval [left, right) denotes all the real numbers x where left <= x < right.
Implement the RangeModule class:
RangeModule()Initializes the object of the data structure.void addRange(int left, int right)Adds the half-open interval[left, right), tracking every real number in that interval. Adding an interval that partially overlaps with currently tracked numbers should add any numbers in the interval[left, right)that are not already tracked.boolean queryRange(int left, int right)Returnstrueif every real number in the interval[left, right)is currently being tracked, andfalseotherwise.void removeRange(int left, int right)Stops tracking every real number currently being tracked in the half-open interval[left, right).
Example 1:
Input [“RangeModule”, “addRange”, “removeRange”, “queryRange”, “queryRange”, “queryRange”] [[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]
Output [null, null, null, true, false, true]
Explanation RangeModule rangeModule = new RangeModule(); rangeModule.addRange(10, 20); rangeModule.removeRange(14, 16); rangeModule.queryRange(10, 14); // return True,(Every number in [10, 14) is being tracked) rangeModule.queryRange(13, 15); // return False,(Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked) rangeModule.queryRange(16, 17); // return True, (The number 16 in [16, 17) is still being tracked, despite the remove operation)
2. Coding Pattern Used in Solution
The provided code in all four languages (C++, Java, JavaScript, and Python) follows the Merge Intervals pattern. This pattern is used to manage and manipulate ranges or intervals, ensuring that overlapping intervals are merged, and operations like adding, querying, and removing ranges are performed efficiently.
3. Code Implementation in Different Languages
3.1 Range Module C++
class RangeModule {
public:
map<int, int> ranges;
RangeModule() {}
void addRange(int left, int right) {
auto it = ranges.upper_bound(left);
while(it != ranges.end() && it->first <= right){
right = max(it->second, right);
++it;
ranges.erase(prev(it));
}
if(it != ranges.begin() && left <= (--it)->second){
it->second = max(it->second, right);
}
else{
ranges[left] = right;
}
}
bool queryRange(int left, int right) {
auto it = ranges.upper_bound(left);
if(it == ranges.begin()) return false;
return prev(it)->second >= right;
}
void removeRange(int left, int right) {
auto it = ranges.lower_bound(left);
int cutEnd = -1;
while(it != ranges.end() && it->first < right){
cutEnd = max(cutEnd, it->second);
it++;
ranges.erase(prev(it));
}
if(it != ranges.begin() && left < (--it)->second){
cutEnd = max(cutEnd, it->second);
it->second = left;
}
if(right<cutEnd){
ranges[right] = cutEnd;
}
}
};
3.2 Range Module Java
class RangeModule {
TreeMap<Integer, Integer> m = new TreeMap<>();
public RangeModule() {}
public void addRange(int s, int e) {
var L = m.floorEntry(s);
var R = m.floorEntry(e);
if (L != null && L.getValue() >= s) s = L.getKey();
if (R != null && R.getValue() > e) e = R.getValue();
m.subMap(s, e).clear();
m.put(s, e);
}
public boolean queryRange(int s, int e) {
var L = m.floorEntry(s);
return L != null && L.getValue() >= e;
}
public void removeRange(int s, int e) {
var L = m.floorEntry(s);
var R = m.floorEntry(e);
if (L != null && L.getValue() > s) m.put(L.getKey(), s);
if (R != null && R.getValue() > e) m.put(e, R.getValue());
m.subMap(s, e).clear();
}
}
3.3 Range Module JavaScript
var RangeModule = function() {
this.intervals = [];
};
RangeModule.prototype.addRange = function(left, right) {
let newInterval = [left, right];
let i = 0;
while(i < this.intervals.length && this.intervals[i][1] < newInterval[0]) {
i++;
}
while(i < this.intervals.length && this.intervals[i][0] <= newInterval[1]) {
newInterval = [Math.min(newInterval[0], this.intervals[i][0]), Math.max(newInterval[1], this.intervals[i][1])];
this.intervals.splice(i, 1);
}
this.intervals.splice(i, 0, newInterval);
};
RangeModule.prototype.queryRange = function(left, right) {
let low = 0;
let high = this.intervals.length-1;
while(low <= high) {
let mid = low + (Math.floor((high - low) / 2));
if(this.intervals[mid][0] <= left && this.intervals[mid][1] >= right) {
return true;
} else if (this.intervals[mid][0] > left) {
high = mid - 1;
} else {
low = mid + 1;
}
}
return false;
};
RangeModule.prototype.removeRange = function(left, right) {
let i = 0;
while(i < this.intervals.length && this.intervals[i][1] < left) {
i++;
}
if(i < this.intervals.length && this.intervals[i][0] < left) {
let newIntervalBefore = [this.intervals[i][0], left];
if(right < this.intervals[i][1]) {
let newIntervalAfter = [right, this.intervals[i][1]];
this.intervals.splice(i, 1, newIntervalBefore, newIntervalAfter);
return;
}
this.intervals.splice(i, 1, newIntervalBefore);
i++;
}
while(i < this.intervals.length && right >= this.intervals[i][1]) {
this.intervals.splice(i, 1);
}
if(i < this.intervals.length && right > this.intervals[i][0]) {
let newIntervalAfter = [right, this.intervals[i][1]];
this.intervals.splice(i, 1, newIntervalAfter);
}
}
3.4 Range Module Python
from bisect import bisect_left as bl, bisect_right as br
class RangeModule:
def __init__(self):
self._X = []
def addRange(self, left, right):
i, j = bl(self._X, left), br(self._X, right)
self._X[i : j] = [left] * (i % 2 == 0) + [right] * (j % 2 == 0)
def queryRange(self, left, right):
i, j = br(self._X, left), bl(self._X, right)
return i == j and i % 2 == 1
def removeRange(self, left, right):
i, j = bl(self._X, left), br(self._X, right)
self._X[i : j] = [left] * (i % 2 == 1) + [right] * (j % 2 == 1)
4. Time and Space Complexity
| Time Complexity | Space Complexity | |
| C++ | O(n + log n) | O(n) |
| Java | O(n + log n) | O(n) |
| JavaScript | O(n + log n) | O(n) |
| Python | O(n + log n) | O(n) |
- The Merge Intervals pattern is used to efficiently manage overlapping ranges.
- The choice of data structure (e.g.,
map,TreeMap, array, or list) affects the implementation details but not the overall complexity significantly. - The operations are efficient for moderate-sized inputs, but for very large inputs, the (O(n)) operations (e.g., merging or splitting ranges) can become a bottleneck.
- The space complexity is O(n) for all implementations, as they store the intervals in a data structure.