Block Placement Queries
Asked at TikTok, Capital One, Roblox
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.
Asked At
| 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).
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
def 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 is described in detail above, including step-by-step walkthroughs, complexity analysis, and solution code in Python. Scroll up to the "Optimal Approach" section.
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).