LeetCode 715: Range Module Solution

Master LeetCode problem 715 (Range Module), a hard challenge, with our optimized solutions in Java, C++, and Python. Explore detailed explanations, test your code in our interactive editor, and prepare for coding interviews.

715. Range Module

Hard

Design Segment Tree Ordered Set

Problem Explanation

Explanation

To solve this problem, we can use a data structure to store the ranges in a sorted order. We can represent each range as a pair of integers [left, right). When adding a new range, we can merge it with existing ranges if it overlaps with them. When querying a range, we can check if all numbers in that range are covered by the stored ranges. When removing a range, we can split existing ranges if they overlap with the range to be removed.

Algorithm:

Initialize an empty list to store the ranges.
Implement the addRange function:
- Iterate through the existing ranges and merge the new range with any overlapping ranges.
- Add the new range to the list.
Implement the queryRange function:
- Iterate through the ranges to check if all numbers in the query range are covered.
Implement the removeRange function:
- Split any ranges that overlap with the range to be removed.

Time Complexity:

Adding/Removing a range: O(N) where N is the number of stored ranges.
Querying a range: O(N) where N is the number of stored ranges.

Space Complexity:

O(N) where N is the number of stored ranges.

Solution Code

class RangeModule {
    List<int[]> ranges;

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

    public void addRange(int left, int right) {
        List<int[]> newRanges = new ArrayList<>();
        int i = 0;
        while (i < ranges.size() && ranges.get(i)[1] < left) {
            newRanges.add(ranges.get(i));
            i++;
        }

        while (i < ranges.size() && ranges.get(i)[0] <= right) {
            left = Math.min(left, ranges.get(i)[0]);
            right = Math.max(right, ranges.get(i)[1]);
            i++;
        }

        newRanges.add(new int[]{left, right});

        while (i < ranges.size()) {
            newRanges.add(ranges.get(i));
            i++;
        }

        ranges = newRanges;
    }

    public boolean queryRange(int left, int right) {
        for (int[] range : ranges) {
            if (range[0] <= left && range[1] >= right) {
                return true;
            }
        }
        return false;
    }

    public void removeRange(int left, int right) {
        List<int[]> newRanges = new ArrayList<>();
        for (int[] range : ranges) {
            if (range[1] <= left || range[0] >= right) {
                newRanges.add(range);
            } else {
                if (range[0] < left) {
                    newRanges.add(new int[]{range[0], left});
                }
                if (range[1] > right) {
                    newRanges.add(new int[]{right, range[1]});
                }
            }
        }
        ranges = newRanges;
    }
}

Try It Yourself

Loading code editor...

Frequently Asked Questions

How to solve LeetCode 715 (Range Module)?

This page provides optimized solutions for LeetCode problem 715 (Range Module) in Java, C++, and Python, along with a detailed explanation and an interactive code editor to test your code.

What is the time complexity of LeetCode 715 (Range Module)?

The time complexity for LeetCode 715 (Range Module) varies by solution. Check the detailed explanation section for specific complexities in Java, C++, and Python implementations.

Can I run code for LeetCode 715 on DevExCode?

Yes, DevExCode provides an interactive code editor where you can write, test, and run your code for LeetCode 715 in Java, C++, or Python.

Back to LeetCode Solutions