In this guide, you will get 3161. Block Placement Queries LeetCode Solution with the best time and space complexity. The solution to Block Placement Queries problem is provided in various programming languages like C++, Java, and Python. This will be helpful for you if you are preparing for placements, hackathons, interviews, or practice purposes. The solutions provided here are very easy to follow and include detailed explanations.
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.
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.
Complexity Analysis
Time Complexity: O(10^5 + n\log 10^5)
Space Complexity: O(10^5 + q)
3161. Block Placement Queries LeetCode Solution in C++
class FenwickTree {
public:
FenwickTree(int n) : vals(n + 1) {}
void maximize(int i, int val) {
while (i < vals.size()) {
vals[i] = max(vals[i], val);
i += lowbit(i);
}
}
int get(int i) const {
int res = 0;
while (i > 0) {
res = max(res, vals[i]);
i -= lowbit(i);
}
return res;
}
private:
vector<int> vals;
static int lowbit(int i) {
return i & -i;
}
};
class Solution {
public:
vector<bool> getResults(vector<vector<int>>& queries) {
const int n = min(50000, static_cast<int>(queries.size()) * 3);
vector<bool> ans;
FenwickTree tree(n + 1);
set<int> obstacles{0, n}; // sentinel values
for (const vector<int>& query : queries) {
const int type = query[0];
if (type == 1) {
const int x = query[1];
obstacles.insert(x);
}
}
for (auto it = obstacles.begin(); std::next(it) != obstacles.end(); ++it) {
const int x1 = *it;
const int x2 = *std::next(it);
tree.maximize(x2, x2 - x1);
}
for (int i = queries.size() - 1; i >= 0; --i) {
const int type = queries[i][0];
const int x = queries[i][1];
if (type == 1) {
const auto it = obstacles.find(x);
if (next(it) != obstacles.end()) // x is not the last element.
tree.maximize(*next(it), *next(it) - *prev(it));
obstacles.erase(it);
} else {
const int sz = queries[i][2];
const auto it = obstacles.upper_bound(x);
const int prev = *std::prev(it);
ans.push_back(tree.get(prev) >= sz || x - prev >= sz);
}
}
ranges::reverse(ans);
return ans;
}
}; /* code provided by PROGIEZ */
3161. Block Placement Queries LeetCode Solution in Java
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;
}
} // code provided by PROGIEZ
3161. Block Placement Queries LeetCode Solution in Python
from sortedcontainers import SortedList
class FenwickTree:
def __init__(self, n: int):
self.vals = [0] * (n + 1)
def maximize(self, i: int, val: int) -> None:
while i < len(self.vals):
self.vals[i] = max(self.vals[i], val)
i += FenwickTree.lowtree(i)
def get(self, i: int) -> int:
res = 0
while i > 0:
res = max(res, self.vals[i])
i -= FenwickTree.lowtree(i)
return res
@staticmethod
def lowtree(i: int) -> int:
return i & -i
class Solution:
def getResults(self, queries: list[list[int]]) -> list[bool]:
n = min(50000, len(queries) * 3)
ans = []
tree = FenwickTree(n + 1)
obstacles = SortedList([0, n]) # sentinel values
for query in queries:
type = query[0]
if type == 1:
x = query[1]
obstacles.add(x)
for x1, x2 in itertools.pairwise(obstacles):
tree.maximize(x2, x2 - x1)
for query in reversed(queries):
type = query[0]
x = query[1]
if type == 1:
i = obstacles.index(x)
next = obstacles[i + 1]
prev = obstacles[i - 1]
obstacles.remove(x)
tree.maximize(next, next - prev)
else:
sz = query[2]
i = obstacles.bisect_right(x)
prev = obstacles[i - 1]
ans.append(tree.get(prev) >= sz or x - prev >= sz)
return ans[::-1] # code by PROGIEZ
