[FIXED] How to speed up obstacle checking algorithm?

Issue

I've been given the following problem: "You want to build an algorithm that allows you to build blocks along a number line, and also to check if a given range is block-free. Specifically, we must allow two types of operations:

1. [1, x] builds a block at position x.
2. [2, x, size] checks whether it's possible to build a block of size size that begins at position x (inclusive). Returns 1 if possible else 0.

Given a stream of operations of types 1 and 2, return a list of outputs for each type 2 operations."

I tried to create a set of blocks so we can lookup in O(1) time, that way for a given operation of type 2, I loop in range(x, x + size) and see if any of those points are in the set. This algorithm runs too slowly and I'm looking for alternative approaches that are faster. I also tried searching the entire set of blocks if the size specified in the type 2 call is greater than len(blocks), but this also times out. Can anyone think of a faster way to do this? I've been stuck on this for a while.

Solution

Store the blocks in a red-black tree (or any self-balancing tree), and when you're given a query, find the smallest element in the tree greater than or equal to x and return 1 if it's greater than x+size. This is O(n + mlogn) where n is the number of blocks, and m is the number of queries.

If you use a simple binary search tree (rather than a self-balancing one), a large test case with blocks at (1, 2, 3, ..., n) will cause your search tree to be very deep and queries will run in linear (rather than logarithmic) time.

Answered By - Paul Hankin

Answer Checked By - Pedro (PHPFixing Volunteer)