DSA problem
Block Placement Queries
You are given an infinite 1-D number line and a sequence of queries. Each query is either [1, x] — place an obstacle at coordinate x — or [2, x, sz] — answer "does there exist an empty (no-obstacle) sub-interval of length sz that lies entirely inside [0, x]?". Initially the line has no obstacles. Return a boolean array with one entry per type-2 query.
A naive approach would simulate the line as a bitmap or array and scan each query, but with coordinates up to 5 * 10^4 and thousands of queries the cumulative scan cost is too slow. The key insight is that the obstacles, viewed as a sorted set, partition [0, x] into a small number of maximal empty gaps. The longest such gap is what every type-2 query is really asking about — and crucially, only the gap whose right boundary is the largest obstacle <= x (or the segment up to the first obstacle if none lies in [0, x]) can extend all the way to x.
The structure we need is an ordered set (a balanced BST / TreeSet) of placed obstacle positions. A type-1 insertion is O(log n). For a type-2 query [x, sz], find the largest obstacle p <= x via a floor lookup. If no such p exists, the entire interval [0, x] is empty so the answer is x + 1 >= sz. Otherwise the candidate empty sub-interval that abuts x is (p, x] of length x - p; but we may also place the block anywhere in earlier gaps, and the longest such earlier gap is between two consecutive obstacles both <= x — which is also retrievable in O(log n) via predecessor lookup, or by tracking the global maximum gap in a Fenwick-tree-style structure keyed by obstacle index.
A simpler offline-friendly variant treats every type-2 query as "is there a gap of length >= sz somewhere inside [0, x]?". For each obstacle position, the gap immediately to its left is p - prev(p); the gap immediately to the right of the rightmost obstacle <= x extends to x. Maintain a sorted set of obstacles and, on each insertion, update the max-gap data structure. With O(log n) insert and O(log n) query the whole problem runs in O((Q + N) log N).
Examples
queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]][false,true,true]queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]][true,true,false]queries = [[2,5,3],[1,4],[2,5,3]][true,false]Constraints
- 1 <= queries.length <= 1.5 * 10^5
- For type-1 queries [1, x]: 1 <= x <= 5 * 10^4
- For type-2 queries [2, x, sz]: 1 <= x <= 5 * 10^4, 1 <= sz <= x + 1
- All x values for type-1 queries are distinct.
- There is at least one query of each kind in some test cases.
4 hints and a full solution walkthrough with step-by-step visualizations are available in the practice editor.