Blocks and Obstacles

Problem

Given an infinite integer number line, you would like to build some blocks and obstacles on it. Specifically, you have to implement code which supports two types of operations:

• [1, x] — builds an obstacle at coordinate x along the number line. It is guaranteed that coordinate x does not contain any obstacles when the operation is performed.
• [2, x, size] — checks whether it’s possible to build a block of size size which ends immediately before x on the number line. For example, if x = 6 and size = 2, this operation checks coordinates 4 and 5. Produces "1" if it is possible (no obstacles at the specified coordinates), or "0" otherwise. Note that this operation does not actually build the block, it only checks.

Given an array of operations containing both types of operations described above, return a binary string representing the outputs for all [2, x, size] operations.

Example

operations = [[1, 2],
              [1, 5],
              [2, 5, 2],
              [2, 6, 3],
              [2, 2, 1],
              [2, 3, 2]]

solution(operations) = "1010"

Walkthrough:

• [1, 2] — obstacle at 2.
• [1, 5] — obstacle at 5.
• [2, 5, 2] — checks coords 3..4 → free → "1".
• [2, 6, 3] — checks coords 3..5 → 5 is blocked → "0".
• [2, 2, 1] — checks coord 1..1 → free → "1".
• [2, 3, 2] — checks coords 1..2 → 2 is blocked → "0".

Output: "1010".

Approach

A [2, x, size] query asks: is there any obstacle in the closed interval [x - size, x - 1]?

Naively scanning every coordinate is too slow when x and size can be large. Instead, store obstacles in a sorted structure and ask a single range question per query.

TreeSet<Integer> (a red-black tree) is perfect:

• add(x) — insert obstacle in O(log n).
• ceiling(low) — smallest obstacle >= low in O(log n).

For a query with range [low, high] where low = x - size, high = x - 1:

• Get c = obstacles.ceiling(low).
• If c == null or c > high, no obstacle lies in the range → append "1".
• Otherwise an obstacle sits inside the range → append "0".

Complexity

• Time: O(N log N) where N is the number of operations.
• Space: O(K) where K is the number of obstacles built.

Solution

import java.util.TreeSet;

class Solution {

    public String solution(int[][] operations) {
        TreeSet<Integer> obstacles = new TreeSet<>();
        StringBuilder out = new StringBuilder();

        for (int[] op : operations) {
            if (op[0] == 1) {
                obstacles.add(op[1]);
            } else {
                int x = op[1];
                int size = op[2];
                int low = x - size;
                int high = x - 1;

                Integer nearest = obstacles.ceiling(low);
                if (nearest == null || nearest > high) {
                    out.append('1');
                } else {
                    out.append('0');
                }
            }
        }

        return out.toString();
    }
}

Why ceiling and not a manual scan

ceiling(low) returns the smallest obstacle that is >= low. If even that smallest one is already past high, the whole window [low, high] is guaranteed empty. No need to look further. This collapses a range-check into one O(log n) lookup.

Edge Cases

• size == 0 — range is empty (low > high), always "1". The ceiling check still works: any non-null result will be > high.
• Negative coordinates — the number line is infinite in both directions; TreeSet<Integer> handles negatives naturally.
• Duplicate obstacle inserts — problem guarantees they won’t happen, so no defensive check needed.