Number Line Block Fits
MediumSimulation · Meta
You maintain an infinite number line on which obstacles are placed one at a time. Process operations in order:
[1, x]: place an obstacle at integer positionx. The position is guaranteed to be empty.[2, x, size]: ask whether a block of lengthsizecan be placed starting atx, i.e. covering the integer positionsx, x + 1, ..., x + size - 1. It fits if none of those positions holds an obstacle. Queries never place anything.
Return a string with one character per type-2 operation, in order: "1" if the block fits and "0" if it does not. Return "" if there are no queries.
Example 1
- Input:
- operations = [[1, 4], [2, 1, 3], [2, 2, 3], [1, 8], [2, 5, 3], [2, 5, 4]]
- Output:
- "1010"
- Explanation
- The block at 1 of size 3 covers 1 to 3 and misses the obstacle at 4, so it fits. Starting at 2 it covers 2 to 4 and hits it. After an obstacle is placed at 8, a size-3 block at 5 covers 5 to 7 and fits, but size 4 reaches 8.
Example 2
- Input:
- operations = [[2, 0, 5]]
- Output:
- "1"
- Explanation
- There are no obstacles yet, so the block fits.
Example 3
- Input:
- operations = [[1, 0], [2, -3, 3], [2, -3, 4]]
- Output:
- "10"
- Explanation
- Starting at -3, size 3 covers -3 to -1 and fits. Size 4 also covers 0, where the obstacle is.
Constraints
1 <= operations.length <= 10^5-10^9 <= x <= 10^91 <= size <= 10^9- No two type-1 operations use the same position