LeetCode #3161 — HARD

Block Placement Queries

Break down a hard problem into reliable checkpoints, edge-case handling, and complexity trade-offs.

Solve on LeetCode
The 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.
Patterns Used
🔍Modified Binary Search→📐Segment Tree→

Roadmap

  1. Brute Force Baseline
  2. Core Insight
  3. Algorithm Walkthrough
  4. Edge Cases
  5. Full Annotated Code
  6. Interactive Study Demo
  7. Complexity Analysis
Step 01

Brute Force Baseline

Problem summary: 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 ith query of type 2, and false otherwise.

Baseline thinking

Start with the most direct exhaustive search. That gives a correctness anchor before optimizing.

Pattern signal: Array · Binary Search · Segment Tree

Example 1

[[1,2],[2,3,3],[2,3,1],[2,2,2]]

Example 2

[[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]

Related Problems

  • Building Boxes (building-boxes)
  • Fruits Into Baskets III (fruits-into-baskets-iii)
Step 02

Core Insight

What unlocks the optimal approach

  • Let <code>d[x]</code> be the distance of the next obstacle after <code>x</code>.
  • For each query of type 2, we just need to check if <code>max(d[0], d[1], d[2], …d[x - sz]) > sz</code>.
  • Use segment tree to maintain <code>d[x]</code>.
Interview move: turn each hint into an invariant you can check after every iteration/recursion step.
Step 03

Algorithm Walkthrough

Iteration Checklist

  1. Define state (indices, window, stack, map, DP cell, or recursion frame).
  2. Apply one transition step and update the invariant.
  3. Record answer candidate when condition is met.
  4. Continue until all input is consumed.
Use the first example testcase as your mental trace to verify each transition.
Step 04

Edge Cases

Minimum Input
Single element / shortest valid input
Validate boundary behavior before entering the main loop or recursion.
Duplicates & Repeats
Repeated values / repeated states
Decide whether duplicates should be merged, skipped, or counted explicitly.
Extreme Constraints
Largest constraint values
Re-check complexity target against constraints to avoid time-limit issues.
Invalid / Corner Shape
Empty collections, zeros, or disconnected structures
Handle special-case structure before the core algorithm path.
Step 05

Full Annotated Code

Source-backed implementations are provided below for direct study and interview prep.

// Accepted solution for LeetCode #3161: Block Placement Queries
class FenwickTree {
  public FenwickTree(int n) {
    vals = new int[n + 1];
  }

  public void add(int i, int val) {
    while (i < vals.length) {
      vals[i] = Math.max(vals[i], val);
      i += lowbit(i);
    }
  }

  public int get(int i) {
    int res = 0;
    while (i > 0) {
      res = Math.max(res, vals[i]);
      i -= lowbit(i);
    }
    return res;
  }

  private int[] vals;

  private static int lowbit(int i) {
    return i & -i;
  }
}

class Solution {
  public List<Boolean> getResults(int[][] queries) {
    final int n = Math.min(50000, queries.length * 3);
    List<Boolean> ans = new ArrayList<>();
    FenwickTree tree = new FenwickTree(n + 1);
    TreeSet<Integer> obstacles = new TreeSet<>(Arrays.asList(0, n)); // sentinel values

    for (int[] query : queries) {
      final int type = query[0];
      if (type == 1) {
        final int x = query[1];
        obstacles.add(x);
      }
    }

    Iterator<Integer> it = obstacles.iterator();
    int x1 = it.next();
    while (it.hasNext()) {
      final int x2 = it.next();
      tree.add(x2, x2 - x1);
      x1 = x2;
    }

    for (int i = queries.length - 1; i >= 0; --i) {
      final int type = queries[i][0];
      final int x = queries[i][1];
      if (type == 1) {
        final Integer next = obstacles.higher(x);
        final Integer prev = obstacles.lower(x);
        if (next != null)
          tree.add(next, next - prev);
        obstacles.remove(x);
      } else {
        final int sz = queries[i][2];
        final int prev = obstacles.floor(x);
        ans.add(tree.get(prev) >= sz || x - prev >= sz);
      }
    }

    Collections.reverse(ans);
    return ans;
  }
}
Step 06

Interactive Study Demo

Use this to step through a reusable interview workflow for this problem.

Press Step or Run All to begin.
Step 07

Complexity Analysis

Time
O(log n)
Space
O(1)

Approach Breakdown

LINEAR SCAN
O(n) time
O(1) space

Check every element from left to right until we find the target or exhaust the array. Each comparison is O(1), and we may visit all n elements, giving O(n). No extra space needed.

BINARY SEARCH
O(log n) time
O(1) space

Each comparison eliminates half the remaining search space. After k comparisons, the space is n/2ᵏ. We stop when the space is 1, so k = log₂ n. No extra memory needed — just two pointers (lo, hi).

Shortcut: Halving the input each step → O(log n). Works on any monotonic condition, not just sorted arrays.
Coach Notes

Common Mistakes

Review these before coding to avoid predictable interview regressions.

Off-by-one on range boundaries

Wrong move: Loop endpoints miss first/last candidate.

Usually fails on: Fails on minimal arrays and exact-boundary answers.

Fix: Re-derive loops from inclusive/exclusive ranges before coding.

Boundary update without `+1` / `-1`

Wrong move: Setting `lo = mid` or `hi = mid` can stall and create an infinite loop.

Usually fails on: Two-element ranges never converge.

Fix: Use `lo = mid + 1` or `hi = mid - 1` where appropriate.

Related Problems
#315Count of Smaller Numbers After Selfhard→#327Count of Range Sumhard→#363Max Sum of Rectangle No Larger Than Khard→#456132 Patternmedium→#493Reverse Pairshard→