Last updated on October 9th, 2024 at 06:21 pm

Here, We see Range Module LeetCode Solution. This Leetcode problem is done in many programming languages like C++, Java, JavaScript, Python, etc. with different approaches.

List of all LeetCode Solution

Range Module LeetCode Solution

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

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)

1. Range Module LeetCode Solution 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;
        }
    }
};

2. Range Module LeetCode Solution 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. Range Module LeetCode Solution 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);
    }
}

4. Range Module LeetCode Solution 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)