Range Module - Leetcode Solution

Problem Statement:

A Range Module is a module that tracks ranges of numbers. Your task is to design and implement a data structure for Range Module with the following operations:

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 an already tracked interval is ignored. If adding a range completely inside an interval, then the intervals split into two non-overlapping intervals should be tracked.

queryRange(int left, int right): Returns true if and only if every real number in the interval [left, right) is currently being tracked.

removeRange(int left, int right): Stops tracking every real number in the interval [left, right).

Example:

RangeModule rangeModule = new RangeModule();
rangeModule.addRange(10, 20);
rangeModule.removeRange(14, 16);
rangeModule.queryRange(10, 14); // returns true
rangeModule.queryRange(13, 15); // returns false
rangeModule.queryRange(16, 17); // returns true

Solution:

To solve this problem, we can maintain a list of non-overlapping intervals. We can insert intervals in sorted order by their start positions. We can use a binary search to efficiently find the position where the new interval should be inserted. When we add a new interval, we can merge it with any overlapping intervals.

When we want to remove an interval, we can split any intervals that overlap with the interval to be removed. We can then remove the interval from the list.

When we want to query whether a range is tracked, we can use a binary search to find the position of the first interval that starts after the range's left endpoint. We can then check whether the previous interval overlaps with the range and whether the range overlaps with the current interval.

Here is the implementation of the RangeModule class in Java:

class Interval {
    int start, end;
    Interval(int start, int end) {
        this.start = start;
        this.end = end;
    }
}

class RangeModule {
    List<Interval> intervals;

    public RangeModule() {
        intervals = new ArrayList<>();
    }

    public void addRange(int left, int right) {
        int i = 0;
        while (i < intervals.size() && intervals.get(i).end <= left) {
            i++;
        }
        while (i < intervals.size() && intervals.get(i).start < right) {
            left = Math.min(left, intervals.get(i).start); // merge
            right = Math.max(right, intervals.get(i).end); // merge
            intervals.remove(i);
        }
        intervals.add(i, new Interval(left, right));
    }

    public boolean queryRange(int left, int right) {
        int i = Collections.binarySearch(intervals, new Interval(left, right),
                (a, b) -> a.start - b.start);
        if (i < 0) {
            i = -(i + 1);
        }
        if (i > 0 && intervals.get(i - 1).end >= right) {
            return true;
        }
        return i < intervals.size() && intervals.get(i).start <= left && intervals.get(i).end >= right;
    }

    public void removeRange(int left, int right) {
        int i = 0;
        while (i < intervals.size() && intervals.get(i).end <= left) {
            i++;
        }
        while (i < intervals.size() && intervals.get(i).start < right) {
            if (intervals.get(i).start < left) {
                intervals.add(i, new Interval(intervals.get(i).start, left)); // split
                i++;
            }
            if (intervals.get(i).end > right) {
                intervals.add(i, new Interval(right, intervals.get(i).end)); // split
                i++;
            }
            intervals.remove(i);
        }
    }
}

The time complexity of addRange, queryRange, and removeRange operations is O(n) in the worst case, where n is the number of intervals in the list. However, in practice, the operations are expected to be much faster because the intervals are sorted and non-overlapping.

1