Number Line Obstacles: Check Whether a Centered Block Can Be Built
Company: Roblox
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: medium
Interview Round: Online Assessment
You are working on an infinite integer number line that starts with no obstacles. Process a sequence of operations of two types:
- `[1, x]` builds an obstacle at coordinate `x`. It is guaranteed that coordinate `x` does not already hold an obstacle when the operation is performed.
- `[2, x, size]` checks whether a block centered on `x` and extending `size - 1` units in each direction could be built, that is, whether none of the coordinates from `x - (size - 1)` to `x + (size - 1)` holds an obstacle. For example, for `x = 0` and `size = 3`, it checks coordinates `-2` through `2`. The check produces `"1"` if the block could be built and `"0"` otherwise. It does not build the block, so it never changes the number line.
Return the outputs of all type-2 operations, in the order the operations appear, concatenated into one string.
### Function Signature
```python
def check_blocks(operations: list[list[int]]) -> str:
```
### Rules
- Operations are processed in the given order. A type-2 operation sees exactly the obstacles built by the type-1 operations that come before it.
- The checked range is inclusive at both ends and contains `2 * size - 1` coordinates. With `size = 1`, only `x` itself is checked.
- Each type-2 operation contributes exactly one character to the result. If there are no type-2 operations, return the empty string `""`.
### Constraints
- `1 <= len(operations) <= 10^5`
- Each operation is either `[1, x]` or `[2, x, size]`.
- `-10^9 <= x <= 10^9`
- `1 <= size <= 10^9`
- No two type-1 operations build at the same coordinate.
- The checked endpoints `x - (size - 1)` and `x + (size - 1)` lie between `-1999999999` and `1999999999`, so they fit in a 32-bit signed integer.
### Examples
**Example 1**
```text
Input: operations = [[1, 2], [2, 0, 3], [2, 0, 2], [1, -5], [2, -3, 3], [2, -3, 2]]
Output: "0101"
```
An obstacle is built at `2`. The check at `0` with size `3` covers `-2` to `2` and hits the obstacle at `2`, giving `"0"`. With size `2` it covers `-1` to `1`, which is clear, giving `"1"`. After an obstacle is built at `-5`, the check at `-3` with size `3` covers `-5` to `-1` and gives `"0"`, while size `2` covers `-4` to `-2` and gives `"1"`.
**Example 2**
```text
Input: operations = [[2, 7, 1], [1, 7], [2, 7, 1], [2, 10, 3], [2, 10, 4]]
Output: "1010"
```
The first check covers only `7`, which is still empty. After the obstacle at `7` is built, the same check gives `"0"`. The check at `10` with size `3` covers `8` to `12` and is clear; with size `4` it covers `7` to `13`, which contains the obstacle.
**Example 3**
```text
Input: operations = [[1, 1000000000], [2, -1000000000, 1000000000], [2, 1, 1000000000]]
Output: "10"
```
The first check covers `-1999999999` to `-1`, which does not contain `1000000000`. The second covers `-999999998` to `1000000000`, and its right end is the obstacle.
Overview: Process operations on an infinite integer number line that either place an obstacle or ask whether a block centered at a point, reaching a given distance in each direction, is free of obstacles, and return the answers as a binary string. It tests efficient online range queries over large, sparse coordinates.
You are working on an infinite integer number line that starts with no obstacles. You are given a list `operations` and must process the operations in order. Each operation has one of two forms:
- `[1, x]` builds an obstacle at coordinate `x`. It is guaranteed that coordinate `x` does not already hold an obstacle when the operation is performed.
- `[2, x, size]` checks whether a block centered on `x` and extending `size - 1` units in each direction could be built, that is, whether none of the coordinates from `x - (size - 1)` to `x + (size - 1)` holds an obstacle. For example, for `x = 0` and `size = 3`, it checks coordinates `-2` through `2`. The check produces `"1"` if the block could be built and `"0"` otherwise. It does not build the block, so it never changes the number line.
Return the outputs of all type-2 operations, in the order the operations appear, concatenated into one string.
**Rules**
- Operations are processed in the given order. A type-2 operation sees exactly the obstacles built by the type-1 operations that come before it.
- The checked range is inclusive at both ends and contains `2 * size - 1` coordinates. With `size = 1`, only `x` itself is checked.
- Each type-2 operation contributes exactly one character to the result. If there are no type-2 operations, return the empty string `""`.
**Example 1**
```text
Input: operations = [[1, 2], [2, 0, 3], [2, 0, 2], [1, -5], [2, -3, 3], [2, -3, 2]]
Output: "0101"
```
An obstacle is built at `2`. The check at `0` with size `3` covers `-2` to `2` and hits the obstacle at `2`, giving `"0"`. With size `2` it covers `-1` to `1`, which is clear, giving `"1"`. After an obstacle is built at `-5`, the check at `-3` with size `3` covers `-5` to `-1` and gives `"0"`, while size `2` covers `-4` to `-2` and gives `"1"`.
**Example 2**
```text
Input: operations = [[2, 7, 1], [1, 7], [2, 7, 1], [2, 10, 3], [2, 10, 4]]
Output: "1010"
```
The first check covers only `7`, which is still empty. After the obstacle at `7` is built, the same check gives `"0"`. The check at `10` with size `3` covers `8` to `12` and is clear; with size `4` it covers `7` to `13`, which contains the obstacle.
**Constraints**
- `1 <= len(operations) <= 10^5`
- Each operation is either `[1, x]` or `[2, x, size]`.
- `-10^9 <= x <= 10^9`
- `1 <= size <= 10^9`
- No two type-1 operations build at the same coordinate.
- For every type-2 operation, the checked endpoints `x - (size - 1)` and `x + (size - 1)` lie between `-1999999999` and `1999999999`, so they fit in a 32-bit signed integer.
No input value or checked endpoint exceeds `2^31 - 1` in absolute value, so 32-bit signed integers are enough for every input.
Constraints
- 1 <= len(operations) <= 10^5
- Each operation is either [1, x] or [2, x, size].
- -10^9 <= x <= 10^9
- 1 <= size <= 10^9
- No two type-1 operations build at the same coordinate.
- For every type-2 operation, the checked endpoints x - (size - 1) and x + (size - 1) lie between -1999999999 and 1999999999, so they fit in a 32-bit signed integer.
Examples
Input: ([[1, 2], [2, 0, 3], [2, 0, 2], [1, -5], [2, -3, 3], [2, -3, 2]],)
Expected Output: '0101'
Explanation: Source example 1: obstacle 2 lies in [-2, 2] but not [-1, 1]; obstacle -5 is the left endpoint of [-5, -1] and outside [-4, -2].
Input: ([[2, 7, 1], [1, 7], [2, 7, 1], [2, 10, 3], [2, 10, 4]],)
Expected Output: '1010'
Explanation: Source example 2: the same size-1 check at 7 flips after the build; [8, 12] is clear but [7, 13] contains 7.
Hints
- A check only cares whether at least one obstacle built so far lies in the inclusive range from x - (size - 1) to x + (size - 1); how many such obstacles there are does not matter.
- Timing matters: a check must ignore every obstacle whose build operation appears later in the list, even one at a coordinate inside its range.
- With up to 10^5 operations, comparing every check against every obstacle built so far can approach 10^10 comparisons, so look for a way to answer each range question faster than a linear scan.