Watch 5 video solutions for Block Placement Queries, a hard level problem involving Array, Binary Search, Binary Indexed Tree. This walkthrough by Aryan Mittal has 8,725 views views. Want to try solving it yourself? Practice on FleetCode or read the detailed text solution.
There exists an infinite number line, with its origin at 0 and extending towards the positive x-axis.
You are given a 2D array queries, which contains two types of queries:
queries[i] = [1, x]. Build an obstacle at distance x from the origin. It is guaranteed that there is no obstacle at distance x when the query is asked.queries[i] = [2, x, sz]. Check if it is possible to place a block of size sz anywhere in the range [0, x] on the line, such that the block entirely lies in the range [0, x]. A block cannot be placed if it intersects with any obstacle, but it may touch it. Note that you do not actually place the block. Queries are separate.Return a boolean array results, where results[i] is true if you can place the block specified in the ith query of type 2, and false otherwise.
Example 1:
Input: queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]]
Output: [false,true,true]
Explanation:
For query 0, place an obstacle at x = 2. A block of size at most 2 can be placed before x = 3.
Example 2:
Input: queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]
Output: [true,true,false]
Explanation:
x = 7 for query 0. A block of size at most 7 can be placed before x = 7.x = 2 for query 2. Now, a block of size at most 5 can be placed before x = 7, and a block of size at most 2 before x = 2.
Constraints:
1 <= queries.length <= 15 * 1042 <= queries[i].length <= 31 <= queries[i][0] <= 21 <= x, sz <= min(5 * 104, 3 * queries.length)x when the query is asked.Problem Overview: You receive a sequence of queries on a number line. Some queries place a block at a position, while others ask whether a block of a given size can fit within a specific boundary without overlapping previously placed blocks. The challenge is answering placement feasibility queries efficiently as the number of blocks grows.
Approach 1: Using a Sorted List or Tree Structure (O(q log n) time, O(n) space)
The key observation is that only the nearest placed blocks around a query boundary matter. Maintain all placed block positions in an ordered structure such as a balanced BST or a sorted list. When a placement query arrives, insert the position while keeping the structure sorted. For a feasibility query, use binary search to find the closest existing blocks around the target boundary and compute the size of the free gap between them.
This gap represents the maximum available continuous space where a new block might fit. If the gap length is greater than or equal to the requested block size, the query returns true. Otherwise, the placement is impossible. Each insertion and neighbor lookup takes O(log n) time, making this approach efficient for large query counts. This method relies heavily on ordered search operations similar to problems involving binary search and interval gaps.
In more advanced implementations, the same idea can be extended with structures like a segment tree or binary indexed tree to track maximum available gaps across ranges. However, for most constraints, maintaining the ordered set of block boundaries is enough and simpler to implement.
Approach 2: Using a HashSet and Linear Scan (O(q · n) time, O(n) space)
A simpler baseline stores all placed blocks inside a HashSet. When a feasibility query appears, scan backward from the boundary to measure how many consecutive free positions exist before hitting a placed block. If the free segment length reaches the required block size, the query succeeds.
This approach is easy to implement and avoids complex data structures. Insertions are O(1) on average, but feasibility checks may scan many positions in the worst case. If the coordinate range is large or queries are frequent, the runtime quickly degrades to O(q · n). This makes it unsuitable for tight constraints but useful as a brute-force baseline to verify correctness.
Recommended for interviews: Interviewers typically expect the ordered structure solution. Recognizing that only the nearest placed blocks determine the usable space shows strong problem decomposition. Implementing the sorted set with binary search achieves O(q log n) time and demonstrates familiarity with ordered data structures and gap-based reasoning. The linear scan approach is still valuable to mention first because it clarifies the problem mechanics before optimizing.
| Approach | Time | Space | When to Use |
|---|---|---|---|
| HashSet with Linear Scan | O(q · n) | O(n) | Small constraints or quick brute-force validation |
| Sorted List / Balanced Tree with Binary Search | O(q log n) | O(n) | General case with many queries and large coordinate range |
| Segment Tree / Binary Indexed Tree Gap Tracking | O(q log n) | O(n) | When queries require fast range gap checks across many segments |