Block Placement Queries - Practice Coding Problems

Block Placement Queries - 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 distance x from the origin. It is guaranteed that there is no obstacle at distance x when 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 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 i-th query of type 2, and false otherwise.

Input & Output

Example 1 — Basic Operations

$ Input: queries = [[1,2],[2,3,3],[2,5,2]]

› Output: [false,true]

💡 Note: Add obstacle at 2. Check if size-3 block fits in [0,3]: gap 0→2 is size 2, gap 2→3 is size 1, max gap < 3, so false. Check if size-2 block fits in [0,5]: gap 2→5 is size 3 ≥ 2, so true.

Example 2 — Multiple Obstacles

$ Input: queries = [[1,1],[1,4],[2,6,2],[2,6,3]]

› Output: [true,false]

💡 Note: Add obstacles at 1 and 4. Check size-2 block in [0,6]: gaps are 0→1(1), 1→4(2), 4→6(2), max gap=2≥2, so true. Check size-3 block: max gap=2<3, so false.

Example 3 — No Obstacles

$ Input: queries = [[2,5,3],[1,2],[2,5,6]]

› Output: [true,false]

💡 Note: Check size-3 block in [0,5] with no obstacles: entire range has size 6≥3, so true. Add obstacle at 2. Check size-6 block: max gap is now 3<6, so false.

Constraints

1 ≤ queries.length ≤ 10⁴
queries[i].length == 2 or 3
1 ≤ x ≤ 5 × 10⁴
1 ≤ sz ≤ 5 × 10⁴

Visualization

Tap to expand

Understanding the Visualization

Input

Queries to add obstacles and check block placements

Process

Track obstacles and calculate available gaps

Output

Boolean array indicating if each block can be placed

Key Takeaway

🎯 Key Insight: Efficiently track gaps between obstacles to quickly determine block placement feasibility

Asked in

G Google 35 a Amazon 28 M Microsoft 22

The key insight is to track gaps between obstacles and find the maximum available space. The optimal approach uses TreeMap/sorted list with binary search for O(q log n) time complexity. Time: O(q log n), Space: O(n).

Common Approaches

Approach	Time	Space	Notes
✓ Brute Force with Set	O(q × x)	O(n)	Store obstacles in a set and check all possible positions for each block placement query
Binary Search with TreeMap	O(q × log n)	O(n)	Use TreeMap to maintain obstacles and binary search to efficiently find gaps
Sorted List with Gap Tracking	O(q × n)	O(n)	Maintain sorted list of obstacles and find largest gap for efficient block placement checking

Brute Force with Set — Algorithm Steps

Store obstacles in a set
For each block placement query, try all possible starting positions
Check if block intersects with any obstacle in the range

Visualization

Tap to expand

Step-by-Step Walkthrough

Add Obstacles

Store obstacle positions in a set

Try All Positions

For each block query, check every possible starting position

Check Intersection

Verify if block overlaps with any obstacle

Code -

solution.c — C

#include <stdio.h>
#include <stdlib.h>
#include <string.h>
#include <stdbool.h>

#define MAX_OBSTACLES 10000
#define MAX_QUERIES 10000

bool solution(int queries[][3], int query_sizes[], int num_queries, bool* results) {
    int obstacles[MAX_OBSTACLES];
    int obstacle_count = 0;
    int result_count = 0;
    
    for (int i = 0; i < num_queries; i++) {
        if (queries[i][0] == 1) {  // Add obstacle
            obstacles[obstacle_count++] = queries[i][1];
        } else {  // Check block placement
            int x = queries[i][1], sz = queries[i][2];
            bool canPlace = false;
            
            // Try all possible starting positions
            for (int start = 0; start <= x - sz; start++) {
                bool valid = true;
                // Check if block [start, start+sz) intersects any obstacle
                for (int pos = start; pos < start + sz && valid; pos++) {
                    for (int j = 0; j < obstacle_count; j++) {
                        if (obstacles[j] == pos) {
                            valid = false;
                            break;
                        }
                    }
                }
                if (valid) {
                    canPlace = true;
                    break;
                }
            }
            
            results[result_count++] = canPlace;
        }
    }
    
    return result_count;
}

int main() {
    // Simple parsing for basic test cases
    int queries[MAX_QUERIES][3];
    int query_sizes[MAX_QUERIES];
    bool results[MAX_QUERIES];
    
    // Mock data for demonstration
    queries[0][0] = 1; queries[0][1] = 2;
    queries[1][0] = 2; queries[1][1] = 3; queries[1][2] = 3;
    queries[2][0] = 2; queries[2][1] = 5; queries[2][2] = 2;
    query_sizes[0] = 2; query_sizes[1] = 3; query_sizes[2] = 3;
    
    int result_count = solution(queries, query_sizes, 3, results);
    
    printf("[");
    for (int i = 0; i < result_count; i++) {
        printf(results[i] ? "true" : "false");
        if (i < result_count - 1) printf(",");
    }
    printf("]\n");
    
    return 0;
}

Time & Space Complexity

Time Complexity

⏱️

O(q × x)

For each query, we may check up to x positions, and there are q queries

✓ Linear Growth

Space Complexity

O(n)

Set stores up to n obstacle positions

⚡ Linearithmic Space

28.5K Views

Medium Frequency

~35 min Avg. Time

890 Likes

Ln 1, Col 1

Smart Actions

💡 Explanation

AI Ready

💡 Suggestion Tab to accept Esc to dismiss

// Output will appear here after running code

Code Editor Closed

Click the red button to reopen

Input & Output

Constraints

Visualization

Related Problems

Common Approaches

Brute Force with Set — Algorithm Steps

Visualization

Code -

Time & Space Complexity

Select Compiler