Block Placement Queries
Block Placement Queries is a hard intervals problem solved with the segment tree pattern.
The best approach, optimal (reverse offline + segment tree), runs in O((q + M) log M) time and O(M + q) space.
Below are 2 approaches in Java, Python, C++ and JavaScript, from brute force (scan the line for every check) up.
Problem
Picture an infinite number line starting at 0 and going right. You process queries in order:
[1, x]: build an obstacle at positionx. There is never already an obstacle there.[2, x, sz]: decide whether a block of lengthszcould be placed somewhere completely inside[0, x]without any obstacle strictly inside it. The block may touch obstacles at its ends. Nothing is actually placed; it is only a check.
Return a list of booleans with one answer per type 2 query, in order.
Examples
Example 1
- Input
queries = [[1, 3], [2, 5, 3], [2, 5, 4], [1, 6], [2, 8, 3]]- Output
[true, false, true]- Why
- With an obstacle at 3, the free stretches inside [0, 5] are [0, 3] and [3, 5]: a block of 3 fits, a block of 4 does not. After adding 6, [0, 8] has stretches of 3, 3 and 2, so 3 fits again.
Example 2
- Input
queries = [[2, 4, 4], [2, 4, 5], [1, 2], [2, 4, 3]]- Output
[true, false, false]- Why
- With no obstacles, [0, 4] holds a block of 4 but not 5. The obstacle at 2 splits it into two stretches of length 2.
Example 3
- Input
queries = [[1, 1], [1, 4], [2, 7, 3], [2, 3, 3]]- Output
[true, false]- Why
- Inside [0, 7] the stretches are 1, 3 and 3. Inside [0, 3] they are 1 and 2, so a block of 3 does not fit.
Constraints
1 <= queries.length <= 1.5 * 10^5queries[i]is[1, x]or[2, x, sz].1 <= x <= min(5 * 10^4, 3 * queries.length)and1 <= sz <= 10^9- No obstacle is built at a position that already has one.
- There is at least one query of type 2.
Solve it here
Write your solution in Java, Python, C++ or JavaScript and run it against the examples, right in the page. Submit runs the hidden tests too and, with a free account, records the solve in your revision log.
Your own testcases: Run checks these, and the expected output comes from our reference solution.
My submissions
Nothing yet. Every Run and Submit you make while signed in shows up here.
| When | Result | Tests | Runtime | Your time | Type |
|---|
Run checks the testcases above (3 examples, or your own). Submit also runs 11 hidden tests and saves the solve to your log. Signed in, every Run and Submit is saved under My submissions; your draft stays in this browser.
Solutions
Try it yourself first. Then compare: each approach lists its idea, the steps, its time and space, and the code in Java, Python, C++ and JavaScript.
| Approach | Time | Space |
|---|---|---|
| Brute force (scan the line for every check) | O(q · M) | O(M) |
| Optimal (reverse offline + segment tree) | O((q + M) log M) | O(M + q) |
1Brute force (scan the line for every check)
O(q · M)Each of the q queries may scan up to M positions.O(M)One boolean per position, plus the answers.Keep a boolean array of obstacle positions. For each type 2 query walk from 1 to x, tracking the last obstacle seen and the largest gap between consecutive obstacles, then add the tail gap up to x.
- Let M be the largest x in the queries; make blocked[0..M].
- Type 1: set blocked[x] = true.
- Type 2: last = 0, best = 0; for p in 1..x, if blocked[p] then best = max(best, p - last) and last = p.
- Finally best = max(best, x - last) and record best >= sz.
class Solution {
public List<Boolean> getResults(int[][] queries) {
int m = 0;
for (int[] q : queries) m = Math.max(m, q[1]);
boolean[] blocked = new boolean[m + 1];
List<Boolean> res = new ArrayList<>();
for (int[] q : queries) {
if (q[0] == 1) {
blocked[q[1]] = true;
} else {
int x = q[1], last = 0, best = 0;
for (int p = 1; p <= x; p++) {
if (blocked[p]) {
best = Math.max(best, p - last);
last = p;
}
}
best = Math.max(best, x - last);
res.add(best >= q[2]);
}
}
return res;
}
}class Solution:
def getResults(self, queries: List[List[int]]) -> List[bool]:
m = max(q[1] for q in queries)
blocked = [False] * (m + 1)
res = []
for q in queries:
if q[0] == 1:
blocked[q[1]] = True
else:
x = q[1]
last = best = 0
for p in range(1, x + 1):
if blocked[p]:
best = max(best, p - last)
last = p
best = max(best, x - last)
res.append(best >= q[2])
return resclass Solution {
public:
vector<bool> getResults(vector<vector<int>>& queries) {
int m = 0;
for (auto& q : queries) m = max(m, q[1]);
vector<bool> blocked(m + 1, false);
vector<bool> res;
for (auto& q : queries) {
if (q[0] == 1) {
blocked[q[1]] = true;
} else {
int x = q[1], last = 0, best = 0;
for (int p = 1; p <= x; p++) {
if (blocked[p]) {
best = max(best, p - last);
last = p;
}
}
best = max(best, x - last);
res.push_back(best >= q[2]);
}
}
return res;
}
};function getResults(queries) {
let m = 0;
for (const q of queries) m = Math.max(m, q[1]);
const blocked = new Array(m + 1).fill(false);
const res = [];
for (const q of queries) {
if (q[0] === 1) {
blocked[q[1]] = true;
} else {
const x = q[1];
let last = 0, best = 0;
for (let p = 1; p <= x; p++) {
if (blocked[p]) {
best = Math.max(best, p - last);
last = p;
}
}
best = Math.max(best, x - last);
res.push(best >= q[2]);
}
}
return res;
}2Optimal (reverse offline + segment tree)
O((q + M) log M)Every query does O(1) segment tree operations of O(log M) each, and union-find with path compression is near-constant per lookup; building takes O(M).O(M + q)The segment tree, the linked list and the union-find each use O(M) memory, and the answers use O(q).Treat 0 as a permanent obstacle and store, at every obstacle p, the gap p - prev(p) to the obstacle on its left. A block fits in [0, x] when max(gap[0..x]) or the tail x - (last obstacle <= x) is at least sz. Start from the final set of obstacles and replay the queries backwards: a type 1 query now removes obstacle x, which merges two gaps (an O(1) linked-list fix plus two segment tree updates). The last obstacle at or before x is found with a union-find in which every non-obstacle points to its left neighbour.
- Let M be the largest x plus one. Mark all obstacles that will ever exist, plus 0.
- Link the obstacles in a doubly linked list (prev/next), put gap[p] = p - prev[p] into a max segment tree, and set up[p] = p for obstacles and p - 1 otherwise.
- Go through the queries from last to first. Type 2: best = max(segMax(0, x), x - find(x)); record best >= sz.
- Type 1: unlink x, set gap[x] = 0, set gap[next] = next - prev if a next obstacle exists, and set up[x] = x - 1.
- Reverse the recorded answers.
class Solution {
public List<Boolean> getResults(int[][] queries) {
int m = 0;
for (int[] q : queries) m = Math.max(m, q[1]);
m += 1;
boolean[] present = new boolean[m];
present[0] = true;
for (int[] q : queries) if (q[0] == 1) present[q[1]] = true;
int size = 1;
while (size < m) size <<= 1;
int[] tree = new int[2 * size];
int[] prev = new int[m], next = new int[m], up = new int[m];
int last = 0;
for (int p = 0; p < m; p++) {
next[p] = -1;
up[p] = present[p] ? p : p - 1;
if (present[p] && p > 0) {
prev[p] = last;
next[last] = p;
tree[size + p] = p - last;
last = p;
}
}
for (int i = size - 1; i >= 1; i--) tree[i] = Math.max(tree[2 * i], tree[2 * i + 1]);
List<Boolean> res = new ArrayList<>();
for (int k = queries.length - 1; k >= 0; k--) {
int[] q = queries[k];
int x = q[1];
if (q[0] == 1) {
int p = prev[x], nx = next[x];
next[p] = nx;
update(tree, size, x, 0);
if (nx != -1) {
prev[nx] = p;
update(tree, size, nx, nx - p);
}
up[x] = x - 1;
} else {
int best = Math.max(query(tree, size, x), x - find(up, x));
res.add(best >= q[2]);
}
}
Collections.reverse(res);
return res;
}
private int find(int[] up, int x) {
int root = x;
while (up[root] != root) root = up[root];
while (up[x] != root) {
int nx = up[x];
up[x] = root;
x = nx;
}
return root;
}
private void update(int[] tree, int size, int i, int v) {
i += size;
tree[i] = v;
for (i >>= 1; i >= 1; i >>= 1) tree[i] = Math.max(tree[2 * i], tree[2 * i + 1]);
}
// maximum of positions 0..r
private int query(int[] tree, int size, int r) {
int best = 0;
for (int l = size, hi = r + size + 1; l < hi; l >>= 1, hi >>= 1) {
if ((l & 1) == 1) best = Math.max(best, tree[l++]);
if ((hi & 1) == 1) best = Math.max(best, tree[--hi]);
}
return best;
}
}class Solution:
def getResults(self, queries: List[List[int]]) -> List[bool]:
m = max(q[1] for q in queries) + 1
present = [False] * m
present[0] = True
for q in queries:
if q[0] == 1:
present[q[1]] = True
size = 1
while size < m:
size <<= 1
tree = [0] * (2 * size)
prev = [0] * m
nxt = [-1] * m
up = [p if present[p] else p - 1 for p in range(m)]
last = 0
for p in range(1, m):
if present[p]:
prev[p] = last
nxt[last] = p
tree[size + p] = p - last
last = p
for i in range(size - 1, 0, -1):
tree[i] = max(tree[2 * i], tree[2 * i + 1])
def update(i: int, v: int) -> None:
i += size
tree[i] = v
i >>= 1
while i:
tree[i] = max(tree[2 * i], tree[2 * i + 1])
i >>= 1
def query(r: int) -> int: # max of positions 0..r
best = 0
lo, hi = size, r + size + 1
while lo < hi:
if lo & 1:
best = max(best, tree[lo])
lo += 1
if hi & 1:
hi -= 1
best = max(best, tree[hi])
lo >>= 1
hi >>= 1
return best
def find(x: int) -> int:
root = x
while up[root] != root:
root = up[root]
while up[x] != root:
up[x], x = root, up[x]
return root
res = []
for q in reversed(queries):
x = q[1]
if q[0] == 1:
p, nx = prev[x], nxt[x]
nxt[p] = nx
update(x, 0)
if nx != -1:
prev[nx] = p
update(nx, nx - p)
up[x] = x - 1
else:
best = max(query(x), x - find(x))
res.append(best >= q[2])
res.reverse()
return resclass Solution {
int size = 1;
vector<int> tree, up;
void update(int i, int v) {
i += size;
tree[i] = v;
for (i >>= 1; i >= 1; i >>= 1) tree[i] = max(tree[2 * i], tree[2 * i + 1]);
}
int query(int r) { // max of positions 0..r
int best = 0;
for (int l = size, hi = r + size + 1; l < hi; l >>= 1, hi >>= 1) {
if (l & 1) best = max(best, tree[l++]);
if (hi & 1) best = max(best, tree[--hi]);
}
return best;
}
int find(int x) {
int root = x;
while (up[root] != root) root = up[root];
while (up[x] != root) {
int nx = up[x];
up[x] = root;
x = nx;
}
return root;
}
public:
vector<bool> getResults(vector<vector<int>>& queries) {
int m = 0;
for (auto& q : queries) m = max(m, q[1]);
m += 1;
vector<bool> present(m, false);
present[0] = true;
for (auto& q : queries) if (q[0] == 1) present[q[1]] = true;
size = 1;
while (size < m) size <<= 1;
tree.assign(2 * size, 0);
up.assign(m, 0);
vector<int> prev(m, 0), next(m, -1);
int last = 0;
for (int p = 0; p < m; p++) {
up[p] = present[p] ? p : p - 1;
if (present[p] && p > 0) {
prev[p] = last;
next[last] = p;
tree[size + p] = p - last;
last = p;
}
}
for (int i = size - 1; i >= 1; i--) tree[i] = max(tree[2 * i], tree[2 * i + 1]);
vector<bool> res;
for (int k = (int)queries.size() - 1; k >= 0; k--) {
auto& q = queries[k];
int x = q[1];
if (q[0] == 1) {
int p = prev[x], nx = next[x];
next[p] = nx;
update(x, 0);
if (nx != -1) {
prev[nx] = p;
update(nx, nx - p);
}
up[x] = x - 1;
} else {
int best = max(query(x), x - find(x));
res.push_back(best >= q[2]);
}
}
reverse(res.begin(), res.end());
return res;
}
};function getResults(queries) {
let m = 0;
for (const q of queries) m = Math.max(m, q[1]);
m += 1;
const present = new Array(m).fill(false);
present[0] = true;
for (const q of queries) if (q[0] === 1) present[q[1]] = true;
let size = 1;
while (size < m) size <<= 1;
const tree = new Int32Array(2 * size);
const prev = new Int32Array(m);
const next = new Int32Array(m).fill(-1);
const up = new Int32Array(m);
let last = 0;
for (let p = 0; p < m; p++) {
up[p] = present[p] ? p : p - 1;
if (present[p] && p > 0) {
prev[p] = last;
next[last] = p;
tree[size + p] = p - last;
last = p;
}
}
for (let i = size - 1; i >= 1; i--) tree[i] = Math.max(tree[2 * i], tree[2 * i + 1]);
const update = (i, v) => {
i += size;
tree[i] = v;
for (i >>= 1; i >= 1; i >>= 1) tree[i] = Math.max(tree[2 * i], tree[2 * i + 1]);
};
const query = (r) => { // max of positions 0..r
let best = 0;
for (let l = size, hi = r + size + 1; l < hi; l >>= 1, hi >>= 1) {
if (l & 1) best = Math.max(best, tree[l++]);
if (hi & 1) best = Math.max(best, tree[--hi]);
}
return best;
};
const find = (x) => {
let root = x;
while (up[root] !== root) root = up[root];
while (up[x] !== root) {
const nx = up[x];
up[x] = root;
x = nx;
}
return root;
};
const res = [];
for (let k = queries.length - 1; k >= 0; k--) {
const q = queries[k];
const x = q[1];
if (q[0] === 1) {
const p = prev[x], nx = next[x];
next[p] = nx;
update(x, 0);
if (nx !== -1) {
prev[nx] = p;
update(nx, nx - p);
}
up[x] = x - 1;
} else {
const best = Math.max(query(x), x - find(x));
res.push(best >= q[2]);
}
}
return res.reverse();
}Edge cases to test
- A type 2 query before any obstacle exists: the whole stretch [0, x] is free
- An obstacle exactly at x: the stretch ending at x still counts in full
- Obstacles to the right of x must be ignored, but the gap from the last obstacle at or before x up to x still counts
- sz far larger than any possible stretch (up to 10^9)
Hints
Hint 1
A block of size sz fits in [0, x] exactly when the longest obstacle-free stretch inside [0, x] is at least sz. Those stretches are the gaps between consecutive obstacles (with 0 acting as an obstacle), plus the tail from the last obstacle at or before x up to x.
Hint 2
Store each gap at the position of the obstacle that ends it. Then the gaps fully inside [0, x] are a prefix of positions, and a range-maximum structure answers the question in O(log M).
Hint 3
Inserting obstacles splits gaps, which needs a predecessor search. Processing the queries backwards turns insertions into removals, where a doubly linked list over positions and a 'nearest obstacle to the left' union-find are enough.
FAQ
What is the best time complexity for Block Placement Queries?
Optimal (reverse offline + segment tree) runs in O((q + M) log M) time and O(M + q) extra space. Every query does O(1) segment tree operations of O(log M) each, and union-find with path compression is near-constant per lookup; building takes O(M).
Which pattern does Block Placement Queries use?
It is a intervals problem that uses the segment tree pattern.
Is there a brute force solution for Block Placement Queries?
Yes. Brute force (scan the line for every check) takes O(q · M) time and O(M) space. Keep a boolean array of obstacle positions.
Which edge cases should I test for Block Placement Queries?
A type 2 query before any obstacle exists: the whole stretch [0, x] is free; An obstacle exactly at x: the stretch ending at x still counts in full; Obstacles to the right of x must be ignored, but the gap from the last obstacle at or before x up to x still counts; sz far larger than any possible stretch (up to 10^9).