Skip to main content
Talentd

Block Placement Queries - Solution & Explanation

HardArrayBinary SearchBinary Indexed TreeSegment Tree8 min readAsked at: Microsoft, Meta, Capital One +7
Practice this problem

Problem Statement

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:

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 = 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.

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.

  1. Use SortedList from the sortedcontainers module to store obstacles efficiently.
  2. Process each query. For type 1, add the obstacle in the SortedList.
  3. For type 2, use binary search (via bisect_right) to find if there exists a large enough gap to place the block.
  4. Add the result of each type 2 query to the results list.

Code

PythonJavaScript

Python

JavaScript

Complexity

Time Complexity: O(log n) for each insertion and query, where n is the number of obstacles.

Space Complexity: O(n), for storing obstacles.

Try this approach in the editor →

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.

  1. Leverage a fixed array for obstacle markers, using the range limits directly.
  2. Iterate over each type 2 query and perform a linear scan over possible segment start points where a block could fit within range.
  3. Check each possible segment and ensure it's free from any obstacles and set result accordingly.
  4. Requires memory for obstacles up to max range, though this scales through the fixed array boundaries.

Code

CC++

C

C++

Complexity

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.

Try this approach in the editor →

Complexity Comparison

ApproachComplexity
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.

Detailed Complexity Analysis

ApproachTimeSpaceWhen to Use
HashSet with Linear ScanO(q · n)O(n)Small constraints or quick brute-force validation
Sorted List / Balanced Tree with Binary SearchO(q log n)O(n)General case with many queries and large coordinate range
Segment Tree / Binary Indexed Tree Gap TrackingO(q log n)O(n)When queries require fast range gap checks across many segments

Video Solution

3161. Block Placement Queries | Fenwick Tree | Segment Tree Lazy Propogation • Aryan Mittal • 10,724 views views

Watch 9 more video solutions →

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.

Ready to solve this problem?

Practice Block Placement Queries with our built-in code editor and test cases.

Practice on FleetCode
Previous

Building Boxes

Next

Fruits Into Baskets III