Model answer
The task
Process queries that add obstacle points on a number line or ask whether a block of a given size can fit within the interval from 0 to a specified coordinate without covering an obstacle. Return a Boolean answer for each placement query.
Key idea
Keep the free gap ending at each obstacle, and track the maximum such gap with a segment tree. For a placement query, also check the final gap from the last obstacle at or before the limit to the limit itself.
Approach
- Coordinate-compress all coordinates mentioned in the queries.
- Use a Fenwick tree to track which compressed coordinates currently contain obstacles.
- On insertion, find the neighboring obstacles; update the gap ending at the new obstacle and the gap ending at its successor.
- For a placement query, take the maximum stored gap up to its coordinate and compare it with the trailing gap.
from typing import List
class Fenwick:
def __init__(self, n: int) -> None:
self.n = n
self.tree = [0] * (n + 1)
def add(self, index: int, delta: int) -> None:
index += 1
while index <= self.n:
self.tree[index] += delta
index += index & -index
def prefix_sum(self, end: int) -> int:
"""Count in indices [0, end)."""
total = 0
while end > 0:
total += self.tree[end]
end -= end & -end
return total
def kth(self, rank: int) -> int:
"""Index of the rank-th active item, using 1-based rank."""
index = 0
step = 1 << (self.n.bit_length() - 1)
while step:
candidate = index + step
if candidate <= self.n and self.tree[candidate] < rank:
index = candidate
rank -= self.tree[candidate]
step >>= 1
return index
class MaxSegmentTree:
def __init__(self, n: int) -> None:
self.size = 1
while self.size < n:
self.size *= 2
self.tree = [0] * (2 * self.size)
def set(self, index: int, value: int) -> None:
index += self.size
self.tree[index] = value
index //= 2
while index:
self.tree[index] = max(self.tree[2 * index],
self.tree[2 * index + 1])
index //= 2
def query(self, left: int, right: int) -> int:
"""Maximum over indices in [left, right)."""
left += self.size
right += self.size
result = 0
while left < right:
if left & 1:
result = max(result, self.tree[left])
left += 1
if right & 1:
right -= 1
result = max(result, self.tree[right])
left //= 2
right //= 2
return result
class Solution:
def getResults(self, queries: List[List[int]]) -> List[bool]:
coords = sorted({query[1] for query in queries})
index_of = {x: i for i, x in enumerate(coords)}
n = len(coords)
active = Fenwick(n)
gaps = MaxSegmentTree(n)
answers = []
for query in queries:
if query[0] == 1:
x = query[1]
i = index_of[x]
# Ignore a repeated insertion.
if active.prefix_sum(i + 1) == active.prefix_sum(i):
before = active.prefix_sum(i)
total = active.prefix_sum(n)
pred_i = active.kth(before) if before else None
succ_i = active.kth(before + 1) if before < total else None
prev_x = coords[pred_i] if pred_i is not None else 0
gaps.set(i, x - prev_x)
if succ_i is not None:
gaps.set(succ_i, coords[succ_i] - x)
active.add(i, 1)
else:
x, size = query[1], query[2]
i = index_of[x]
# Last obstacle at or before x determines the trailing gap.
count = active.prefix_sum(i + 1)
prev_i = active.kth(count) if count else None
prev_x = coords[prev_i] if prev_i is not None else 0
trailing_gap = x - prev_x
best_gap = max(gaps.query(0, i + 1), trailing_gap)
answers.append(best_gap >= size)
return answers
Complexity:
- Time: O(q log q), for coordinate compression and logarithmic tree operations per query.
- Space: O(q), for compressed coordinates and the trees.
Common follow-ups
- How would you handle obstacle removal? Update the two affected neighboring gaps when removing an obstacle.
- What if coordinates are too large to compress offline? Use a dynamic segment tree over the coordinate range.
- What if blocks must fit in a specified subinterval? Query gaps intersecting that interval and account for its clipped boundaries.