Range Module

This page explains Java solution to problem Range Module using TreeMap data structure.

Problem Statement

A Range Module is a module that tracks ranges of numbers. Your task is to design and implement the following interfaces in an efficient manner.

• 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.
• 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 currently being tracked in the interval [left, right).

addRange(10, 20): null
removeRange(14, 16): null
queryRange(10, 14): true (Every number in [10, 14) is being tracked)
queryRange(13, 15): false (Numbers like 14, 14.03, 14.17 in [13, 15) are not being tracked)
queryRange(16, 17): true (The number 16 in [16, 17) is still being tracked, despite the remove operation)

Solution

package com.vc.hard;

import java.util.*;

class RangeModule {

    private TreeMap<Integer, Integer> rangeMap;

    public RangeModule() {
        rangeMap = new TreeMap<Integer, Integer>();
    }

    public void addRange(int left, int right) {
        Integer pre = rangeMap.floorKey(left);
        Integer next = rangeMap.floorKey(right);

        if(pre != null && rangeMap.get(pre) >= left) {
            left = pre;
        }

        if(next != null && rangeMap.get(next) > right) {
            right = rangeMap.get(next);
        }

        rangeMap.subMap(left, true, right, true).clear();
        rangeMap.put(left, right);
    }

    public boolean queryRange(int left, int right) {
        Integer pre = rangeMap.floorKey(left);
        if(pre != null && rangeMap.get(pre) >= right) return true;
        else return false;
    }

    public void removeRange(int left, int right) {
        Integer pre = rangeMap.floorKey(left);
        Integer next = rangeMap.floorKey(right);

        if(next != null && rangeMap.get(next) > right) {
            rangeMap.put(right, rangeMap.get(next));
        }

        if(pre != null && rangeMap.get(pre) >= left) {
            rangeMap.put(pre, left);
        }

        rangeMap.subMap(left, true, right, false).clear();
    }
}

/**
 * Your RangeModule object will be instantiated and called as such:
 * RangeModule obj = new RangeModule();
 * obj.addRange(left,right);
 * boolean param_2 = obj.queryRange(left,right);
 * obj.removeRange(left,right);
 */

Time Complexity

addRange(int left, int right): O(log N)
queryRange(int left, int right): O(log N)
removeRange(int left, int right): O(log N) Where
N is total number of ranges in a RangeModule

Space Complexity

O(N) Where
N is total number of ranges in a RangeModule