Block Placement Queries
Understanding the Problem
We have a number line starting at 0, with an obstacle already at position 0. We process queries one by one. Type 1 queries add obstacles, and type 2 queries ask: "Can I fit a block of a given size somewhere in the range [0, x]?"
Obstacles are points and a block is a segment that may touch obstacles at its ends, so the longest block that fits between consecutive obstacles at positions a and b has size b - a. A type 2 query reduces to: among the gaps between consecutive obstacles in [0, x], including the final stretch from the last obstacle up to x, is any gap at least sz?
The gaps change as obstacles arrive, and each type 2 query only looks at the prefix [0, x] rather than the whole line. So we need a structure that supports dynamic insertions and answers maximum-gap queries over a prefix.
One property keeps the updates manageable: adding an obstacle never enlarges a gap. It splits one gap into two smaller pieces and leaves every other gap untouched, so each insertion changes the gap structure in only two places.
Key Constraints:
queries.length <= 15000-- Re-scanning every gap per query is O(n^2), around 2.25 * 10^8 operations in the worst case, which is borderline. A per-query cost of O(log n) or O(log M) is the target.- Positions up to
5 * 10^4-- The coordinate space is small enough to index a segment tree directly by position, with no coordinate compression needed. - Obstacle at position 0 exists initially -- Every gap has an obstacle on its left, which keeps the gap bookkeeping uniform.
Approach 1: Brute Force (Sorted Set + Linear Scan)
Intuition
Maintain a sorted set of all obstacle positions. For a type 2 query, walk through the obstacles in [0, x] in increasing order, compute the gap between each consecutive pair, and check whether any gap reaches sz.
One gap does not lie between two obstacles: the stretch from the last obstacle at or before x up to x itself. A block can end exactly at x, so this trailing gap counts too and gets checked separately.
Algorithm
- Initialize a sorted set containing position 0.
- For each query:
- If type 1 (query[0] == 1): insert the obstacle position query[1] into the sorted set.
- If type 2 (query[0] == 2): iterate through all obstacles in [0, query[1]] in order, compute each gap, and check if any gap >= query[2]. Also check the gap from the last obstacle to query[1].
- Collect results for all type 2 queries.
Example Walkthrough
Code
- Time Complexity: O(n^2) in the worst case. A type 2 query scans every obstacle at or before x, and there can be O(n) of them. Insertions into the ordered structure cost at most O(n) each.
- Space Complexity: O(n) for the obstacle positions.
The bottleneck is the linear scan in each type 2 query. The next approach keeps every gap in a segment tree, so the maximum gap in [0, x] comes from a single logarithmic-time range query instead of a scan.
Approach 2: Segment Tree + Sorted Set (Optimal)
Intuition
Build a segment tree indexed by position on the number line. At each obstacle position, store the gap from that obstacle back to its predecessor, so every gap lives at its right endpoint. Inserting an obstacle at position p splits one gap, and the sorted set identifies which one: find the neighbors prev and next of p. The old gap next - prev, stored at next, becomes two gaps: p - prev stored at p, and next - p stored at next. Two point updates record the change.
A type 2 query becomes a range max query over positions [0, x], which returns the largest gap among the obstacles in that prefix. The trailing gap is x - last, where last is the largest obstacle position at or before x, found in the sorted set. The answer is true when either value reaches sz.
Each gap is stored at its right endpoint, the obstacle that closes it. A range max over positions [0, x] therefore counts a gap only when its right endpoint is at most x, which means the entire gap lies inside [0, x]. A gap that straddles x is excluded from the query, and its usable part, from the last obstacle at or before x up to x, is exactly the trailing gap computed separately. So max(range max, trailing gap) is the longest free stretch available inside [0, x].
Algorithm
- Compute the maximum position that appears in any query.
- Initialize a segment tree over the position range [0, maxPos] supporting point updates and range max queries.
- Initialize a sorted set with obstacle at position 0.
- For each query:
- Type 1 (add obstacle at p): Find
prevandnextneighbors in the sorted set. Insert p. Update segment tree: set gap at p top - prev, and ifnextexists, set gap at next tonext - p. - Type 2 (check block of size sz in [0, x]): Query segment tree for max gap in [0, x]. Find last obstacle at or before x, compute trailing gap = x - last. Answer is true if max(segment tree max, trailing gap) >= sz.
Example Walkthrough
Code
- Time Complexity: O(n log M), where n is the number of queries and M is the maximum position (up to 5 * 10^4). A type 1 query does two segment tree point updates at O(log M) each, plus an ordered-set insert. A type 2 query does one range max query at O(log M) plus a predecessor lookup.
- Space Complexity: O(M + n). The segment tree uses O(M) space and the obstacle set uses O(n).