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.
This approach involves maintaining a sorted list or tree set of obstacles to efficiently find intervals without obstacles. As obstacles are inserted, the data structure updates automatically, allowing us to quickly determine viable positions for block placements in the range [0, x] using binary search or range queries.
SortedList from the sortedcontainers module to store obstacles efficiently.SortedList.bisect_right) to find if there exists a large enough gap to place the block.Python
JavaScript
Time Complexity: O(log n) for each insertion and query, where n is the number of obstacles.
Space Complexity: O(n), for storing obstacles.
This approach involves using a simple hash set to track obstacles, then linearly scanning the range [0, x] for each type 2 query to check for a valid block placement area. This approach is less efficient but conceptually straightforward.
Time Complexity: O(n * x) for each type 2 query, where x is the maximum position we scan.
Space Complexity: O(n), where n is the number of obstacles represented in the array.
| Approach | Complexity |
|---|---|
| Approach 1: Using a Sorted List or Tree Structure | Time Complexity: O(log n) for each insertion and query, where n is the number of obstacles. Space Complexity: O(n), for storing obstacles. |
| Approach 2: Using a HashSet and Linear Scan | Time Complexity: O(n * x) for each type 2 query, where x is the maximum position we scan. Space Complexity: O(n), where n is the number of obstacles represented in the array. |
| 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 |
3161. Block Placement Queries | Fenwick Tree | Segment Tree Lazy Propogation • Aryan Mittal • 8,725 views views
Watch 4 more video solutions →Practice Block Placement Queries with our built-in code editor and test cases.
Practice on FleetCode