Range Module - Practice Coding Problems

Range Module - Problem

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

Input & Output

Example 1 — Basic Operations

$ Input: operations = ["RangeModule", "addRange", "removeRange", "queryRange", "queryRange"], params = [[], [10, 20], [14, 16], [10, 14], [13, 15]]

› Output: [null, null, null, true, false]

💡 Note: RangeModule initializes empty. addRange(10, 20) tracks [10, 20). removeRange(14, 16) removes [14, 16), leaving [10, 14) and [16, 20). queryRange(10, 14) returns true (fully covered). queryRange(13, 15) returns false (15 not tracked).

Example 2 — Overlapping Ranges

$ Input: operations = ["RangeModule", "addRange", "addRange", "queryRange"], params = [[], [10, 15], [12, 18], [10, 18]]

› Output: [null, null, null, true]

💡 Note: addRange(10, 15) tracks [10, 15). addRange(12, 18) merges with existing to track [10, 18). queryRange(10, 18) returns true (fully covered).

Example 3 — Edge Case Empty Query

$ Input: operations = ["RangeModule", "queryRange"], params = [[], [1, 5]]

› Output: [null, false]

💡 Note: Empty RangeModule has no tracked ranges, so queryRange(1, 5) returns false.

Constraints

1 ≤ left < right ≤ 10⁹
At most 10⁴ calls will be made to addRange, queryRange, and removeRange.

Visualization

Tap to expand

Understanding the Visualization

Add Ranges

Track half-open intervals [left, right)

Query Coverage

Check if range is fully tracked

Remove Ranges

Stop tracking specified intervals

Key Takeaway

🎯 Key Insight: Use interval merging to efficiently manage overlapping ranges and enable fast coverage queries

Asked in

G Google 15 f Facebook 12 a Amazon 8

The key insight is to maintain non-overlapping intervals and merge them efficiently. Best approach uses interval merging with O(n) time for operations and O(n) space for storing intervals.

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Set	O(n)	O(n)	Store every individual number in a set
Interval Merging	O(n)	O(n)	Store disjoint intervals and merge overlapping ones

Brute Force with Set — Algorithm Steps

Store individual numbers in a set
Add/remove numbers one by one
Query by checking each number exists

Visualization

Tap to expand

Step-by-Step Walkthrough

Initialize

Create empty set

Add Range

Add each number individually

Query/Remove

Check/remove each number individually

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

typedef struct {
    int* tracked;
    int capacity;
    int size;
} RangeModule;

RangeModule* rangeModuleCreate() {
    RangeModule* rm = (RangeModule*)malloc(sizeof(RangeModule));
    rm->tracked = (int*)malloc(1000 * sizeof(int));
    rm->capacity = 1000;
    rm->size = 0;
    return rm;
}

void rangeModuleAddRange(RangeModule* rm, int left, int right) {
    for (int i = left; i < right; i++) {
        // Simple implementation - add if not exists
        bool found = false;
        for (int j = 0; j < rm->size; j++) {
            if (rm->tracked[j] == i) {
                found = true;
                break;
            }
        }
        if (!found && rm->size < rm->capacity) {
            rm->tracked[rm->size++] = i;
        }
    }
}

bool rangeModuleQueryRange(RangeModule* rm, int left, int right) {
    for (int i = left; i < right; i++) {
        bool found = false;
        for (int j = 0; j < rm->size; j++) {
            if (rm->tracked[j] == i) {
                found = true;
                break;
            }
        }
        if (!found) return false;
    }
    return true;
}

void rangeModuleRemoveRange(RangeModule* rm, int left, int right) {
    for (int i = left; i < right; i++) {
        for (int j = 0; j < rm->size; j++) {
            if (rm->tracked[j] == i) {
                // Remove by shifting
                for (int k = j; k < rm->size - 1; k++) {
                    rm->tracked[k] = rm->tracked[k + 1];
                }
                rm->size--;
                break;
            }
        }
    }
}

int main() {
    printf("[null]\n");
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(n)

Each operation may process up to n individual numbers

✓ Linear Growth

Space Complexity

O(n)

Set stores up to n individual numbers

⚡ Linearithmic Space

32.1K Views

Medium Frequency

~35 min Avg. Time

856 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Set — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler