LeetCode Solutions Blog

Block Placement Queries

Number: 3435

Difficulty: Hard

Paid? No

Problem Description

Given an infinite number line starting at 0 (extending only along the positive x‑axis), you are asked to handle two types of queries:

For a query of type 1, given as [1, x], build (place) an obstacle at position x. It is guaranteed that there is no obstacle at x when this query is issued.
For a query of type 2, given as [2, x, sz], determine if it is possible to place a block of length sz anywhere in the interval [0, x] such that the block (which may touch but not intersect any obstacle) lies completely in [0, x].

Return a boolean array corresponding to the type 2 queries where each entry is true if it is possible to place such a block, and false otherwise.

Key Insights

Placing obstacles on the number line splits [0, x] into free intervals.
A block of length sz can be placed if at least one free interval (or a truncated free interval at the boundary x) has length at least sz.
Using a segment tree that “remembers” the longest contiguous free segment is a great way to support both dynamic updates (when an obstacle is added) and range queries (to check for a large enough free interval).
In the segment tree, each node will store: • prefix length: the contiguous free segment starting at the left end, • suffix length: the contiguous free segment ending at the right end, • best: the maximum free contiguous interval within the segment, • total: the length (number of positions) of the segment.
For an update (type 1 query), we mark the position as blocked (i.e. “0”) and update the tree.
For a query (type 2), we query the segment tree for the range [0, x] and check if the “best” free length is at least sz.

Space and Time Complexity

Time Complexity:

Update (placing an obstacle): O(log M) per update, where M is the maximum possible position (here, M ≤ 50000).
Query (checking free interval): O(log M) per query.

Space Complexity: O(M) to store the segment tree.

Solution

We solve the problem by modeling the positions [0, M] (with M equal to the maximum x encountered in the queries) in a segment tree. Initially, all positions are free. Each leaf node of the segment tree represents a single position, and its values (prefix, suffix, best) are initialized to 1. When an obstacle is placed at a position x, we update that leaf to 0 (blocked). The segment tree nodes merge their children’s values so that each node accurately reflects: • prefix: if the entire left child is free, then the free length extends into the right child’s prefix, • suffix: similarly using the right child, • best: the larger of the left child’s best, the right child’s best, or a combination of the left child’s suffix and the right child’s prefix. For a query, we fetch the node information for the interval [0, x] and check if the best free contiguous segment length is at least sz.

Code Solutions

# Python solution using Segment Tree

# A segment tree node which holds the computed free lengths.
class SegmentTreeNode:
    def __init__(self, start, end):
        self.start = start              # left index of the segment
        self.end = end                  # right index of the segment
        self.total = end - start + 1    # total number of positions in the segment
        self.prefix = self.total        # contiguous free length from the start
        self.suffix = self.total        # contiguous free length up to the end
        self.best = self.total          # maximum contiguous free length in this segment
        self.left = None              # left child
        self.right = None             # right child

# Segment Tree class that supports update and query.
class SegmentTree:
    def __init__(self, start, end):
        self.root = self.build(start, end)
        
    def build(self, start, end):
        node = SegmentTreeNode(start, end)
        if start == end:
            return node
        mid = (start + end) // 2
        node.left = self.build(start, mid)
        node.right = self.build(mid + 1, end)
        return node
    
    def update(self, node, idx, value):
        # Update the node corresponding to idx with value (1 for free, 0 for blocked)
        if node.start == node.end:
            node.prefix = value
            node.suffix = value
            node.best = value
            return
        if idx <= node.left.end:
            self.update(node.left, idx, value)
        else:
            self.update(node.right, idx, value)
        # Merge left and right children
        node.prefix = node.left.prefix
        if node.left.prefix == node.left.total:
            node.prefix = node.left.total + node.right.prefix
        node.suffix = node.right.suffix
        if node.right.suffix == node.right.total:
            node.suffix = node.right.total + node.left.suffix
        node.best = max(node.left.best, node.right.best, node.left.suffix + node.right.prefix)
        
    def query(self, node, l, r):
        # Return a tuple: (prefix, suffix, best, total) for the query interval [l, r]
        if node.start > r or node.end < l:
            return (0, 0, 0, 0)
        if l <= node.start and node.end <= r:
            return (node.prefix, node.suffix, node.best, node.total)
        left_res = self.query(node.left, l, r)
        right_res = self.query(node.right, l, r)
        total = left_res[3] + right_res[3]
        prefix = left_res[0]
        if left_res[0] == left_res[3]:
            prefix = left_res[3] + right_res[0]
        suffix = right_res[1]
        if right_res[1] == right_res[3]:
            suffix = right_res[3] + left_res[1]
        best = max(left_res[2], right_res[2], left_res[1] + right_res[0])
        return (prefix, suffix, best, total)

# Class to handle block placement queries.
class BlockPlacement:
    def __init__(self, max_x):
        self.max_x = max_x
        self.segment_tree = SegmentTree(0, max_x)
        
    def build_obstacle(self, x):
        # When an obstacle is built, mark the position as blocked (0)
        self.segment_tree.update(self.segment_tree.root, x, 0)
        
    def can_place_block(self, x, sz):
        # Query the segment tree for range [0, x] and check if best free segment >= sz.
        res = self.segment_tree.query(self.segment_tree.root, 0, x)
        return res[2] >= sz

def blockPlacementQueries(queries):
    # Find maximum x in queries to initialize the segment tree.
    M = 0
    for q in queries:
        if q[0] == 1 or q[0] == 2:
            M = max(M, q[1])
    bp = BlockPlacement(M)
    results = []
    for q in queries:
        if q[0] == 1:
            bp.build_obstacle(q[1])
        else:
            results.append(bp.can_place_block(q[1], q[2]))
    return results

# Example:
# print(blockPlacementQueries([[1,2],[2,3,3],[2,3,1],[2,2,2]]))