Algorithm

Problem Name: 715. Range Module

Problem Link: https://leetcode.com/problems/range-module/
 

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)

 

Constraints:

  • 1 <= left < right <= 109
  • At most 104 calls will be made to addRange, queryRange, and removeRange.

Code Examples

#1 Code Example with Javascript Programming

Code - Javascript Programming


const RangeModule = function() {
  this.range = []
}

RangeModule.prototype.addRange = function(left, right) {
  let index1 = this.range.length
  let low = 0
  let high = this.range.length - 1
  while (low <= high) {
    const mid = (low + high) >> 1
    if (this.range[mid][1] >= left) {
      index1 = Math.min(index1, mid)
      high = mid - 1
    } else {
      low = mid + 1
    }
  }

  let index2 = -1
  low = 0
  high = this.range.length - 1
  while (low  < = high) {
    const mid = (low + high) >> 1
    if (this.range[mid][0]  < = right) {
      index2 = Math.max(index2, mid)
      low = mid + 1
    } else {
      high = mid - 1
    }
  }

  if (index1 === this.range.length) {
    this.range.push([left, right])
    return
  } else if (index2 === -1) {
    this.range.unshift([left, right])
    return
  }
  left = Math.min(left, this.range[index1][0])
  right = Math.max(right, this.range[index2][1])
  this.range.splice(index1, index2 - index1 + 1, [left, right])
}

RangeModule.prototype.queryRange = function(left, right) {
  let index = -1
  let low = 0
  let high = this.range.length - 1
  while (low <= high) {
    const mid = (low + high) >> 1
    if (this.range[mid][0]  < = left) {
      index = Math.max(index, mid)
      low = mid + 1
    } else {
      high = mid - 1
    }
  }
  if (index === -1 || this.range[index][1] < right) {
    return false
  }
  return true
}

RangeModule.prototype.removeRange = function(left, right) {
  let index1 = this.range.length
  let low = 0
  let high = this.range.length - 1
  while (low <= high) {
    const mid = (low + high) >> 1
    if (this.range[mid][1] >= left) {
      index1 = Math.min(index1, mid)
      high = mid - 1
    } else {
      low = mid + 1
    }
  }

  let index2 = -1
  low = 0
  high = this.range.length - 1
  while (low  < = high) {
    const mid = (low + high) >> 1
    if (this.range[mid][0] <= right) {
      index2 = Math.max(index2, mid)
      low = mid + 1
    } else {
      high = mid - 1
    }
  }

  if (index1 === this.range.length || index2 === -1) {
    return
  }

  const newRange = []
  if (left > this.range[index1][0]) {
    newRange.push([this.range[index1][0], left])
  }
  if (right < this.range[index2][1]) {
    newRange.push([right, this.range[index2][1]])
  }
  this.range.splice(index1, index2 - index1 + 1, ...newRange)
}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"] [[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]

Output

x
–
+
cmd
[null, null, null, true, false, true]

#2 Code Example with Python Programming

Code - Python Programming


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)
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"] [[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]

Output

x
–
+
cmd
[null, null, null, true, false, true]

#3 Code Example with C# Programming

Code - C# Programming


using System;
using System.Collections.Generic;
using System.Linq;

namespace LeetCode
{
    public class _0715_RangeModule
    {
        private readonly SortedList < int, int> list;

        public _0715_RangeModule()
        {
            list = new SortedList<int, int>();
        }

        public void AddRange(int left, int right)
        {
            var leftIndex = GetIndex(left);
            if (leftIndex >= 0) left = list.Keys[leftIndex];
            else leftIndex = ~leftIndex;

            var rightIndex = GetIndex(right);
            if (rightIndex >= 0) right = list.Values[rightIndex];
            else rightIndex = ~rightIndex - 1;

            for (int i = leftIndex; i  < = rightIndex; i++)
                list.RemoveAt(leftIndex);

            list[left] = right;
        }

        public bool QueryRange(int left, int right)
        {
            var leftIndex = GetIndex(left);
            var rightIndex = GetIndex(right);
            return leftIndex == rightIndex && leftIndex >= 0;
        }

        public void RemoveRange(int left, int right)
        {
            var leftIndex = GetIndex(left);
            var rightIndex = GetIndex(right);

            if (rightIndex >= 0)
                list[right] = list.Values[rightIndex];
            else
                rightIndex = ~rightIndex - 1;

            if (leftIndex >= 0)
            {
                list[list.Keys[leftIndex]] = left;
                leftIndex++;
            }
            else
                leftIndex = ~leftIndex;

            for (int i = leftIndex; i  < = rightIndex; i++)
                list.RemoveAt(leftIndex);
        }

        private int GetIndex(int value)
        {
            var index = Array.BinarySearch(list.Keys.ToArray(), value);
            if (index >= 0) return index;

            index = ~index;
            if (index > 0 && list.Values[index - 1] >= value)
                return index - 1;
            else
                return ~index;
        }
    }

}
Copy The Code & Try With Live Editor

Input

x
–
+
cmd
["RangeModule", "addRange", "removeRange", "queryRange", "queryRange", "queryRange"] [[], [10, 20], [14, 16], [10, 14], [13, 15], [16, 17]]

Output

x
–
+
cmd
[null, null, null, true, false, true]
Advertisements

Demonstration

Previous
#714 Leetcode Best Time to Buy and Sell Stock with Transaction Fee Solution in C, C++, Java, JavaScript, Python, C# Leetcode
Next
#717 Leetcode 1-bit and 2-bit Characters Solution in C, C++, Java, JavaScript, Python, C# Leetcode