In this guide, you will get 715. Range Module LeetCode Solution with the best time and space complexity. The solution to Range Module problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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) Returns true if every real number in the interval [left, right) is currently being tracked, and false otherwise.
void removeRange(int left, int right) Stops tracking every real number currently being tracked in the half-open interval [left, right).
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)
Constraints:
1 <= left < right <= 109
At most 104 calls will be made to addRange, queryRange, and removeRange.
Complexity Analysis
Time Complexity: O(\log 10^9)
Space Complexity: O(n)
715. Range Module LeetCode Solution in C++
struct SegmentTreeNode {
int lo;
int hi;
bool tracked = false;
std::unique_ptr<SegmentTreeNode> left;
std::unique_ptr<SegmentTreeNode> right;
SegmentTreeNode(int lo, int hi, bool tracked,
std::unique_ptr<SegmentTreeNode> left = nullptr,
std::unique_ptr<SegmentTreeNode> right = nullptr)
: lo(lo),
hi(hi),
tracked(tracked),
left(std::move(left)),
right(std::move(right)) {}
};
class SegmentTree {
public:
explicit SegmentTree() : root(make_unique<SegmentTreeNode>(0, 1e9, false)) {}
void addRange(int i, int j) {
update(root, i, j, true);
}
bool queryRange(int i, int j) {
return query(root, i, j);
}
void removeRange(int i, int j) {
update(root, i, j, false);
}
private:
std::unique_ptr<SegmentTreeNode> root;
void update(std::unique_ptr<SegmentTreeNode>& root, int i, int j,
bool tracked) {
if (root->lo == i && root->hi == j) {
root->tracked = tracked;
root->left = nullptr;
root->right = nullptr;
return;
}
const int mid = root->lo + (root->hi - root->lo) / 2;
if (root->left == nullptr) {
root->left = make_unique<SegmentTreeNode>(root->lo, mid, root->tracked);
root->right =
make_unique<SegmentTreeNode>(mid + 1, root->hi, root->tracked);
}
if (j <= mid)
update(root->left, i, j, tracked);
else if (i > mid)
update(root->right, i, j, tracked);
else {
update(root->left, i, mid, tracked);
update(root->right, mid + 1, j, tracked);
}
root->tracked = merge(root->left->tracked, root->right->tracked);
}
bool query(std::unique_ptr<SegmentTreeNode>& root, int i, int j) const {
if (root->left == nullptr)
return root->tracked;
if (root->lo == i && root->hi == j)
return root->tracked;
const int mid = root->lo + (root->hi - root->lo) / 2;
if (j <= mid)
return query(root->left, i, j);
if (i > mid)
return query(root->right, i, j);
return merge(query(root->left, i, mid), query(root->right, mid + 1, j));
}
bool merge(bool left, bool right) const {
return left && right;
}
};
class RangeModule {
public:
void addRange(int left, int right) {
tree.addRange(left, right - 1);
}
bool queryRange(int left, int right) {
return tree.queryRange(left, right - 1);
}
void removeRange(int left, int right) {
tree.removeRange(left, right - 1);
}
private:
SegmentTree tree;
}; /* code provided by PROGIEZ */
715. Range Module LeetCode Solution in Java
class RangeModule {
public:
void addRange(int left, int right) {
const auto [l, r] = getOverlapRanges(left, right);
if (l == r) { // There's no overlap.
ranges[left] = right; // Add a new range.
return;
}
auto last = r;
const int newLeft = min(l->first, left);
const int newRight = max((--last)->second, right);
ranges.erase(l, r);
ranges[newLeft] = newRight; // Add a new range.
}
bool queryRange(int left, int right) {
auto it = ranges.upper_bound(left);
return it != ranges.begin() && (--it)->second >= right;
}
void removeRange(int left, int right) {
const auto [l, r] = getOverlapRanges(left, right);
if (l == r) // There's no overlap.
return;
auto last = r;
const int newLeft = min(l->first, left);
const int newRight = max((--last)->second, right);
ranges.erase(l, r);
// Add new ranges if needed.
if (newLeft < left)
ranges[newLeft] = left;
if (right < newRight)
ranges[right] = newRight;
}
private:
using IT = map<int, int>::iterator;
map<int, int> ranges;
pair<IT, IT> getOverlapRanges(int left, int right) {
// Point to the first element with `second` >= `left`.
IT l = ranges.upper_bound(left);
// Point to the first element with `first` > `right`.
IT r = ranges.upper_bound(right);
if (l != ranges.begin() && (--l)->second < left)
++l;
return {l, r};
}
}; // code provided by PROGIEZ
715. Range Module LeetCode Solution in Python
class RangeModule {
public void addRange(int left, int right) {
Integer l = ranges.floorKey(left);
Integer r = ranges.floorKey(right);
if (l != null && ranges.get(l) >= left)
left = l;
if (r != null && ranges.get(r) > right)
right = ranges.get(r);
ranges.subMap(left, right).clear();
ranges.put(left, right);
}
public boolean queryRange(int left, int right) {
Integer l = ranges.floorKey(left);
return l == null ? false : ranges.get(l) >= right;
}
public void removeRange(int left, int right) {
Integer l = ranges.floorKey(left);
Integer r = ranges.floorKey(right);
if (r != null && ranges.get(r) > right)
ranges.put(right, ranges.get(r));
if (l != null && ranges.get(l) > left)
ranges.put(l, left);
ranges.subMap(left, right).clear();
}
private TreeMap<Integer, Integer> ranges = new TreeMap<>();
} # code by PROGIEZ
