Block Placement Queries solution and explanation
Google
9 more videos on this problem
3161. Block Placement Queries | Fenwick Tree | Segment Tree Lazy PropogationAryan Mittal · 51:16 · 10K views
Block Placement Queries | Leetcode 3161 | Brute Force | Optimal | Detailed | codestorywithMIKcodestorywithMIK · 55:03 · 9K views
3161. Block Placement Queries (Leetcode Hard)Programming Live with Larry · 1:09:42 · 2K views
Leetcode 3161 | Block Placement Queries | Leetcode POTD | Segment tree + Binary Search | DSACode With Vick · 40:55 · 1K views
3161. Block Placement Queries | Leetcode Daily - PythonLeetcode Daily · 4:37 · 1K views
Block Placement Queries | Leetcode 3161 | Java | HindiKernel Queen 👑 · 22:10 · 750 views
Daily Leetcode #2251: May 30, 2026 - 3161. Block Placement QueriesProgramming Live with Larry · 36:59 · 737 views
Block Placement Queries | Leetcode - 3161Shivam Gupta · 26:26 · 701 views
Block Placement Queries | LeetCode 3161 - Pythonimpoldev · 21:19 · 563 views
DECODEDSA#LEVELUP#CONTESTSOL#leetcode#challengeL.C3161. Block Placement QueriesDecode · 17:23 · 240 views
The problem
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:
- For a query of type 1,
queries[i] = [1, x]. Build an obstacle at distancexfrom the origin. It is guaranteed that there is no obstacle at distancexwhen the query is asked. - For a query of type 2,
queries[i] = [2, x, sz]. Check if it is possible to place a block of sizeszanywhere 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:
- Place an obstacle at
x = 7for query 0. A block of size at most 7 can be placed beforex = 7. - Place an obstacle at
x = 2for query 2. Now, a block of size at most 5 can be placed beforex = 7, and a block of size at most 2 beforex = 2.
Constraints:
1 <= queries.length <= 15 * 1042 <= queries[i].length <= 31 <= queries[i][0] <= 21 <= x, sz <= min(5 * 104, 3 * queries.length)- The input is generated such that for queries of type 1, no obstacle exists at distance
xwhen the query is asked. - The input is generated such that there is at least one query of type 2.
Approach overview
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 1: Approach 1: Using a Sorted List or Tree Structure
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.
def canPlaceBlocks(queries):
from sortedcontainers import SortedList
obstacles = SortedList()
result = []
for q in queries:
if q[0] == 1:
# Add obstacle
obstacles.add(q[1])
elif q[0] == 2:
x, sz = q[1], q[2]
idx = obstacles.bisect_right(x-sz)
can_place = (idx == 0 or obstacles[idx-1] <= x - sz)
can_place = (idx == len(obstacles) or obstacles[idx] >= x)
result.append(can_place)
return resultfunction canPlaceBlocks(queries) {
const SortedSet = require('collections/sorted-set');
const obstacles = new SortedSet();
const result = [];
for (let query of queries) {
if (query[0] === 1) {
// Add obstacle
obstacles.add(query[1]);
} else {
const [_, x, sz] = query;
let idx = obstacles.leastGreaterThan(x - sz);
let can_place = (idx === null || obstacles.len(idx) <= x - sz);
can_place &= (idx === null || obstacles.len(idx) >= x);
result.push(can_place);
}
}
return result;
}- Use
SortedListfrom thesortedcontainersmodule to store obstacles efficiently. - Process each query. For type 1, add the obstacle in the
SortedList. - For type 2, use binary search (via
bisect_right) to find if there exists a large enough gap to place the block. - Add the result of each type 2 query to the results list.
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: Approach 2: Using a HashSet and Linear Scan
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.
#include <vector>
#include <unordered_set>
std::vector<bool> canPlaceBlocks(const std::vector<std::vector<int>>& queries) {
std::unordered_set<int> obstacles;
std::vector<bool> result;
for (const auto& q : queries) {
if (q[0] == 1) {
// Add obstacle
obstacles.insert(q[1]);
} else if(q[0] == 2) {
int x = q[1], sz = q[2];
bool canPlace = false;
for (int start = 0; start + sz <= x; ++start) {
bool isFree = true;
for (int pos = start; pos < start + sz; ++pos) {
if (obstacles.count(pos)) {
isFree = false;
break;
}
}
if (isFree) {
canPlace = true;
break;
}
}
result.push_back(canPlace);
}
}
return result;
}#include <stdio.h>
#include <stdlib.h>
#include <stdbool.h>
#include <string.h>
bool* canPlaceBlocks(int** queries, int queriesSize, int* queriesColSize, int* returnSize) {
int obstacles[50000] = {0}; // Large enough range
bool* result = malloc(queriesSize * sizeof(bool));
*returnSize = 0;
for (int i = 0; i < queriesSize; i++) {
if (queries[i][0] == 1) {
// Add obstacle
obstacles[queries[i][1]] = 1;
} else { // Query is of type 2
int x = queries[i][1];
int sz = queries[i][2];
bool canPlace = false;
for (int j = 0; j <= x; j++) {
if (j + sz <= x) {
bool isFree = true;
for (int k = j; k < j + sz; k++) {
if (obstacles[k]) {
isFree = false;
break;
}
}
if (isFree) {
canPlace = true;
break;
}
}
}
result[(*returnSize)++] = canPlace;
}
}
return result;
}- Use an
unordered_setto store and track obstacles encountered. - Check each potential valid placement position by iterating through potential start points for the block.
- This straightforward linearly scanning method evaluates each possible location, managing simplicity over efficiency.
- Append placement success or failure to the result vector as needed for each query type 2.
Time Complexity: O(x * n) for each check, considering all possibilities across possible positions.
Space Complexity: O(n) for obstacle storage.
Complexity comparison
| 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(x * n) for each check, considering all possibilities across possible positions. Space Complexity: O(n) for obstacle storage. |
Complexity analysis
| 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 |
Frequently asked questions
Is Block Placement Queries easy or hard?
Block Placement Queries is classified as Hard due to the need for dynamic interval reasoning and efficient query handling. A naive scan works conceptually but fails performance constraints, pushing candidates to use ordered structures and binary search.
Block Placement Queries Python/Java solution
Python solutions typically use a sorted list with the bisect module or third‑party SortedList structures. Java implementations rely on TreeSet for ordered storage. Both approaches perform insertion and neighbor search in O(log n) time.
How to solve Block Placement Queries in O(q log n)?
Store all placed block coordinates in a sorted list or balanced tree. For a feasibility query, binary search finds the closest blocks around the boundary and calculates the size of the free interval between them. If the interval length is at least the requested block size, the placement is valid.
What is the best approach for Block Placement Queries?
The most efficient approach maintains placed block positions in a sorted structure such as a balanced tree or sorted list. Binary search finds the nearest neighbors around the query boundary and computes the available gap. Each operation runs in O(log n), giving an overall complexity of O(q log n) for q queries.
Is Block Placement Queries asked at Google/Amazon/Meta?
Problems involving dynamic interval gaps and ordered sets frequently appear in interviews at companies like Google, Amazon, and Meta. Variations often test understanding of binary search on ordered structures, segment trees, or interval management techniques.
What data structure is used in Block Placement Queries?
The common data structures are ordered sets (balanced BST), sorted lists with binary search, and occasionally segment trees or binary indexed trees for tracking maximum free gaps. These structures allow efficient neighbor lookup and dynamic updates.
What is the time complexity of Block Placement Queries?
The optimal solution using an ordered set or balanced tree processes each query in O(log n) time. Insertions and neighbor lookups both rely on binary search. Overall complexity is O(q log n) time with O(n) space to store placed block positions.