3161. Block Placement Queries
Asked at TikTok, Capital One, Roblox
Difficulty
Hard
Time
O((q + M) log M)
Space
O(M)
Pattern
Array
Companies
3
Problem
You have an infinite number line that starts at 0 and goes to the right. There are no obstacles at the start.
You get a list of queries. Each query is one of two kinds:
[1, x]— put an obstacle at positionx. It is guaranteed that no obstacle is already there.[2, x, sz]— ask: can a block of lengthszbe placed somewhere inside[0, x]? The block must lie fully inside[0, x], and it must not overlap any obstacle. Touching an obstacle at its edge is allowed. The block is not actually placed, so later queries are not affected.
Return a list of booleans, one for each type-2 query, in the order the queries appear. A value is true if the block fits, false otherwise. The key idea: inside [0, x], the free space is split into gaps between obstacles (treat 0 as an obstacle too). The block fits exactly when the largest gap in [0, x] is at least sz.
Gaps decide the answer
Constraints
- ●
1 <= queries.length <= 15 * 10^4 - ●
2 <= queries[i].length <= 3 - ●
1 <= queries[i][0] <= 2 - ●
1 <= x, sz <= min(5 * 10^4, 3 * queries.length) - ●
For type-1 queries, no obstacle exists at distance x when the query is asked - ●
There is at least one type-2 query
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]Asked At
3 companies| Company | Difficulty | |
|---|---|---|
| TikTok | Hard | View all TikTok questions → |
| Capital One | Hard | View all Capital One questions → |
| Roblox | Hard | View all Roblox questions → |
How to Think About It
Within [0, x], the free gaps are the distances between consecutive obstacles (treating 0 as an obstacle), plus the tail from the last obstacle p <= x to x. A block fits iff the largest of these is at least sz.
Store each gap at the position of the obstacle that ends it: gap[p] = p - previousObstacle. Then "largest gap before p" is a range-maximum query on [0, p] — a segment tree.
Key insight: insertions split gaps, which needs predecessor and successor lookups in a changing set. Process queries in reverse instead: start with all obstacles present, and each type-1 query becomes a removal that merges two gaps.
Removals-only lets you find the nearest remaining obstacle to the left and right with union-find ("skip to the next alive position"), which is simpler than a balanced tree.
For a type-2 query (x, sz) in reverse: p = nearest obstacle <= x; the answer is max(segMax(0, p), x - p) >= sz. Collect answers and reverse them at the end.
Optimal Approach
Step 1: Let M be the largest coordinate. Mark 0 and every obstacle as alive; set gap[p] = p - prevAlive(p) in a max segment tree.
Step 2: Build union-find arrays prv (largest alive <= p) and nxt (smallest alive >= p, with M + 1 as a sentinel).
Step 3: For each query in reverse:
Type 2 (x, sz): p = findPrev(x); record max(segMax(0, p), x - p) >= sz.
Type 1 (x): remove x (prv[x] = x - 1, nxt[x] = x + 1, gap[x] = 0); a = findPrev(x), b = findNext(x); if b <= M, set gap[b] = b - a.
Step 4: Return the recorded answers in original order.
Time: O((q + M) log M). Space: O(M).
Reverse the queries, remove obstacles
What Trips People Up in Real Interviews
Scanning all obstacles for each query — O(q²).
Forgetting the tail gap from the last obstacle before x up to x itself.
Treating a block that touches an obstacle as blocked. Touching is allowed, so a gap of exactly sz works.
Processing forward with a plain sorted list: insertions are O(n) each. Either use a balanced BST or the reverse-order trick.
Forgetting that 0 acts as an implicit obstacle (the left boundary).
Solution Code
O((q + M) log M) timedef getResults(queries):
M = max(q[1] for q in queries) + 1
alive = [False] * (M + 2)
alive[0] = True
alive[M + 1] = True
for q in queries:
if q[0] == 1:
alive[q[1]] = True
size = 1
while size < M + 1:
size *= 2
seg = [0] * (2 * size)
def update(i, v):
i += size
seg[i] = v
i //= 2
while i:
seg[i] = max(seg[2 * i], seg[2 * i + 1])
i //= 2
def query(lo, hi):
res = 0
lo += size
hi += size + 1
while lo < hi:
if lo & 1:
res = max(res, seg[lo]); lo += 1
if hi & 1:
hi -= 1; res = max(res, seg[hi])
lo //= 2
hi //= 2
return res
prv = [i if alive[i] else i - 1 for i in range(M + 2)]
nxt = [i if alive[i] else i + 1 for i in range(M + 2)]
def find(par, x):
root = x
while par[root] != root:
root = par[root]
while par[x] != root:
par[x], x = root, par[x]
return root
last = 0
for p in range(1, M + 1):
if alive[p]:
update(p, p - last)
last = p
res = []
for q in reversed(queries):
if q[0] == 2:
x, sz = q[1], q[2]
p = find(prv, x)
res.append(max(query(0, p), x - p) >= sz)
else:
x = q[1]
prv[x] = x - 1
nxt[x] = x + 1
update(x, 0)
a, b = find(prv, x), find(nxt, x)
if b <= M:
update(b, b - a)
return res[::-1]Frequently Asked Questions
What is the Block Placement Queries problem?
Block Placement Queries mixes two operations on a number line starting at 0: place an obstacle at `x`, or ask whether a block of size `sz` fits somewhere inside `[0, x]` without crossing an obstacle (touching is allowed). The answer to a query is whether the largest free gap within `[0, x]` is at least `sz`. The clean solution processes queries in reverse, so obstacles are only ever removed.
How do you solve Block Placement Queries?
The optimal approach runs in O((q + M) log M) time and O(M) space. Scroll up to "Optimal Approach" for the step-by-step walkthrough, diagrams, and code in Python, C++ and Java.
What companies ask Block Placement Queries?
Block Placement Queries is asked at TikTok, Capital One, Roblox. It is a hard difficulty problem.
What are common mistakes on Block Placement Queries?
- Scanning all obstacles for each query — `O(q²)`.
- Forgetting the tail gap from the last obstacle before `x` up to `x` itself.
- Treating a block that touches an obstacle as blocked. Touching is allowed, so a gap of exactly `sz` works.
- Processing forward with a plain sorted list: insertions are `O(n)` each. Either use a balanced BST or the reverse-order trick.
- Forgetting that 0 acts as an implicit obstacle (the left boundary).