# Block Placement Queries **Difficulty:** HARD [External](https://leetcode.com/problems/block-placement-queries) Canonical: https://scaleengineer.com/dsa/problems/block-placement-queries **Algorithms:** [Binary Search](https://scaleengineer.com/algorithms/binary-search) **Data structures:** Array, Binary Indexed Tree, Segment Tree **Companies:** [Roblox](https://scaleengineer.com/companies/roblox), [Visa](https://scaleengineer.com/companies/visa), [Capital One](https://scaleengineer.com/companies/capital-one), [Autodesk](https://scaleengineer.com/companies/autodesk), [PayPay](https://scaleengineer.com/companies/paypay), [SIG](https://scaleengineer.com/companies/sig) --- ## 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: 1. For a query of type 1, `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. 2. For a query of type 2, `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:** **![](https://assets.glich.co/dsa/block-placement-queries/image0.png)** 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:** **![](https://assets.glich.co/dsa/block-placement-queries/image1.png)** * Place an obstacle at `x = 7` for query 0\. A block of size at most 7 can be placed before `x = 7`. * Place an obstacle at `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 * 104` * `2 <= queries[i].length <= 3` * `1 <= queries[i][0] <= 2` * `1 <= x, sz <= min(5 * 104, 3 * queries.length)` * The input is generated such that for queries of type 1, no obstacle exists at distance `x` when the query is asked. * The input is generated such that there is at least one query of type 2. # Approaches ## Brute Force Simulation This approach directly simulates the problem statement. For each type 1 query, we record the new obstacle's position. For each type 2 query, we gather all obstacles within the query's range `[0, x]`, sort them, and then iterate through the sorted positions to find the largest available gap. This largest gap is then compared with the required block size. **Time:** O(Q_1 + Q_2 * Q_1 * log(Q_1)), where Q_1 and Q_2 are the counts of type 1 and type 2 queries, respectively. In the worst case where Q_1 ≈ Q and Q_2 ≈ Q, this becomes O(Q^2 log Q). · **Space:** O(Q_1), where Q_1 is the number of type 1 queries, to store the obstacle positions. **Pros:** Simple to understand and implement.; Correct for small inputs. **Cons:** Extremely inefficient due to re-filtering and re-sorting obstacles for every type 2 query.; Will result in a 'Time Limit Exceeded' error for larger test cases. ### Explanation We use a standard `List` to store the positions of all obstacles as they are added. When a type 1 query `[1, pos]` arrives, we simply append `pos` to our list. For a type 2 query `[2, x, sz]`, we need to determine the largest contiguous empty space within the `[0, x]` interval. To do this, we first construct a new list containing `0` and all obstacle positions from our main list that are less than or equal to `x`. We then sort this new list to get an ordered set of points that define the boundaries of available segments. The largest gap is found by calculating the difference between each pair of consecutive points in the sorted list, and also the difference between `x` and the last point. The maximum of these values gives the size of the largest block that can be placed. If this size is at least `sz`, the query result is `true`. ```java import java.util.ArrayList; import java.util.Collections; import java.util.List; class Solution { public List getResults(int[][] queries) { List obstacles = new ArrayList<>(); List results = new ArrayList<>(); for (int[] query : queries) { if (query[0] == 1) { obstacles.add(query[1]); } else { int x = query[1]; int sz = query[2]; List currentPoints = new ArrayList<>(); currentPoints.add(0); for (int obs : obstacles) { if (obs <= x) { currentPoints.add(obs); } } Collections.sort(currentPoints); int maxGap = 0; for (int i = 1; i < currentPoints.size(); i++) { maxGap = Math.max(maxGap, currentPoints.get(i) - currentPoints.get(i - 1)); } maxGap = Math.max(maxGap, x - currentPoints.get(currentPoints.size() - 1)); results.add(maxGap >= sz); } } return results; } } ``` ### Algorithm - Maintain a simple list of all obstacle positions. - For a type 1 query `[1, pos]`, add `pos` to the list of obstacles. - For a type 2 query `[2, x, sz]`: 1. Create a temporary list of relevant points, initially containing `0`. 2. Iterate through all obstacles placed so far. Add any obstacle with position `<= x` to this temporary list. 3. Sort the temporary list. 4. Iterate through the sorted list to find the maximum gap between consecutive points. Let the sorted points be `p_0, p_1, ..., p_k`. The gaps are `p_1 - p_0, p_2 - p_1, ..., p_k - p_{k-1}`. 5. Also, calculate the gap from the last point `p_k` to `x`, which is `x - p_k`. 6. The largest possible block size is the maximum of all these calculated gaps. 7. Compare this maximum size with `sz` to determine if the block can be placed. ## Optimized Iteration with a Sorted Set This approach improves upon the brute-force method by using a sorted data structure, such as a `TreeSet` in Java, to maintain the obstacle positions. This avoids the costly step of re-sorting for every query. Adding an obstacle is efficient. However, finding the maximum gap for a type 2 query still requires iterating through all relevant obstacles. **Time:** O(Q_1 * log(Q_1) + Q_2 * Q_1). Adding an obstacle takes O(log Q_1). A type 2 query iterates through up to O(Q_1) obstacles. In the worst case, this is O(Q^2). · **Space:** O(Q_1) to store the obstacles in the `TreeSet`. **Pros:** Faster than the pure brute-force approach by avoiding repeated sorting.; Relatively easy to implement using standard library data structures. **Cons:** While better than brute-force, it still requires a linear scan over a subset of obstacles for each type 2 query, making it too slow for the given constraints.; The complexity is quadratic in the worst-case scenario. ### Explanation By storing obstacle positions in a `TreeSet`, we ensure they are always kept in sorted order. A type 1 query `[1, pos]` becomes a simple `add` operation on the `TreeSet`, which takes logarithmic time. For a type 2 query `[2, x, sz]`, we can find the maximum gap more efficiently than the brute-force approach. We iterate through the obstacles in the `TreeSet` that are at or before position `x`. We can get a view of this subset of obstacles using `headSet(x, true)`. We traverse these obstacles, keeping track of the previous position (`last_pos`, initialized to 0) to calculate the gap size. The maximum gap found during this iteration is recorded. Finally, we account for the gap between the last relevant obstacle and `x`. The overall maximum gap is then compared to `sz`. ```java import java.util.ArrayList; import java.util.List; import java.util.TreeSet; class Solution { public List getResults(int[][] queries) { TreeSet obstacles = new TreeSet<>(); List results = new ArrayList<>(); for (int[] query : queries) { if (query[0] == 1) { obstacles.add(query[1]); } else { int x = query[1]; int sz = query[2]; int maxGap = 0; int lastPos = 0; // Add 0 to the set for calculation, but it's implicitly handled by lastPos=0 for (int obs : obstacles.headSet(x, true)) { maxGap = Math.max(maxGap, obs - lastPos); lastPos = obs; } maxGap = Math.max(maxGap, x - lastPos); results.add(maxGap >= sz); } } return results; } } ``` ### Algorithm - Use a `TreeSet` to store obstacle positions, which keeps them sorted automatically. - For a type 1 query `[1, pos]`, add `pos` to the `TreeSet`. - For a type 2 query `[2, x, sz]`: 1. Initialize `max_gap = 0` and `last_pos = 0`. 2. Iterate through the obstacles in the `TreeSet` that are less than or equal to `x`. This can be done efficiently using `TreeSet.headSet(x, true)`. 3. For each obstacle `obs`, calculate the gap `obs - last_pos` and update `max_gap`. Then, set `last_pos = obs`. 4. After the loop, calculate the final gap from the last obstacle to `x`, which is `x - last_pos`, and update `max_gap`. 5. Compare `max_gap` with `sz` for the result. ## Efficient Queries with Segment Tree This is a highly efficient approach that leverages a segment tree to quickly query for the maximum gap size. The core idea is to maintain the lengths of all gaps between consecutive obstacles in a data structure that supports fast range maximum queries and point updates. A segment tree is perfectly suited for this. By combining it with a `TreeSet` to keep track of obstacle locations, we can process both types of queries in logarithmic time. **Time:** O(Q * (log Q + log M)), where Q is the number of queries and M is the maximum coordinate. Each query involves a few `TreeSet` (O(log Q)) and segment tree (O(log M)) operations. · **Space:** O(Q_1 + M), where Q_1 is the number of obstacles and M is the maximum coordinate value. O(Q_1) for the `TreeSet` and O(M) for the segment tree. **Pros:** Highly efficient, with logarithmic time complexity per query.; Scales well for large inputs and passes within the time limits.; Provides a general framework for solving problems involving dynamic gap management. **Cons:** Significantly more complex to implement than the previous approaches.; Requires a good understanding of segment trees. ### Explanation To solve this problem efficiently, we need to quickly answer the question: 'What is the largest available space in `[0, x]`?'. This space is determined by the maximum of two quantities: 1) the largest gap between two consecutive obstacles within `[0, x]`, and 2) the gap from the last obstacle in `[0, x]` to `x`. A `TreeSet` helps us find the last obstacle and its neighbors efficiently. A segment tree helps us find the maximum internal gap. We build the segment tree over the coordinate space. Each leaf `i` of the tree stores the length of the gap that ends at position `i`. An internal node stores the maximum gap length in its corresponding range. When an obstacle at `p` is added (Type 1), it splits a gap `(prev, next)`. We update our segment tree by changing the gap lengths associated with endpoints `p` and `next`. This is a point update operation, which is `O(log M)`. When we check for placing a block (Type 2), we query the segment tree for the maximum value in `[0, x]` to get the largest internal gap. This is a range query, also `O(log M)`. We also find the gap to `x` using the `TreeSet` in `O(log Q_1)`. The maximum of these two values gives us our answer. ```java import java.util.ArrayList; import java.util.List; import java.util.TreeSet; class SegmentTree { private int[] tree; private int n; public SegmentTree(int size) { this.n = size; this.tree = new int[4 * n]; } public void update(int node, int start, int end, int idx, int val) { if (start == end) { tree[node] = val; return; } int mid = start + (end - start) / 2; if (start <= idx && idx <= mid) { update(2 * node + 1, start, mid, idx, val); } else { update(2 * node + 2, mid + 1, end, idx, val); } tree[node] = Math.max(tree[2 * node + 1], tree[2 * node + 2]); } public int query(int node, int start, int end, int l, int r) { if (r < start || end < l || l > r) { return 0; } if (l <= start && end <= r) { return tree[node]; } int mid = start + (end - start) / 2; int p1 = query(2 * node + 1, start, mid, l, r); int p2 = query(2 * node + 2, mid + 1, end, l, r); return Math.max(p1, p2); } } class Solution { public List getResults(int[][] queries) { int maxCoord = 0; for (int[] q : queries) { maxCoord = Math.max(maxCoord, q[1]); } maxCoord++; SegmentTree st = new SegmentTree(maxCoord); TreeSet obstacles = new TreeSet<>(); obstacles.add(0); List results = new ArrayList<>(); for (int[] query : queries) { if (query[0] == 1) { int p = query[1]; Integer prev = obstacles.floor(p); Integer next = obstacles.ceiling(p); if (next != null) { st.update(0, 0, maxCoord - 1, next, next - p); } st.update(0, 0, maxCoord - 1, p, p - prev); obstacles.add(p); } else { int x = query[1]; int sz = query[2]; int maxInternalGap = st.query(0, 0, maxCoord - 1, 0, x); Integer lastObs = obstacles.floor(x); int gapToX = x - lastObs; results.add(Math.max(maxInternalGap, gapToX) >= sz); } } return results; } } ``` ### Algorithm - Use a `Segment Tree` data structure built over the range of possible coordinates `[0, M]`, where `M` is the maximum coordinate value from the input. - The segment tree will store the maximum gap length. Specifically, at leaf index `p`, we store the length of the gap that ends at position `p`. - Use a `TreeSet` to maintain the sorted positions of obstacles. - **Type 1 Query `[1, p]`**: When adding an obstacle `p`, it splits an existing gap. Find its neighbors `prev_obs` and `next_obs` from the `TreeSet`. The gap `(prev_obs, next_obs)` is replaced by `(prev_obs, p)` and `(p, next_obs)`. Update the segment tree: set the value at index `p` to `p - prev_obs` and the value at index `next_obs` to `next_obs - p`. Then add `p` to the `TreeSet`. - **Type 2 Query `[2, x, sz]`**: The maximum block size is the larger of two values: 1. The maximum gap between any two consecutive obstacles both located at or before `x`. This is found by querying the segment tree for the maximum value in the range `[0, x]`. 2. The gap from the last obstacle before `x` to `x` itself. This is found using `TreeSet.floor(x)`. - Compare the result with `sz`.