3161. Block Placement Queries

3161. Block Placement Queries

Difficulty: Hard

Topics: Principal, Array, Binary Search, Binary Indexed Tree, Segment Tree, Biweekly Contest 131

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 iᵗʰ 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 * 10⁴
• 2 <= queries[i].length <= 3
• 1 <= queries[i][0] <= 2
• 1 <= x, sz <= min(5 * 10⁴, 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.

Hint:

1. Let d[x] be the distance of the next obstacle after x.
2. For each query of type 2, we just need to check if max(d[0], d[1], d[2], …d[x - sz]) > sz.
3. Use segment tree to maintain d[x].

Solution:

The problem involves handling two types of queries on an infinite positive number line:

• Type 1: Place an obstacle at a given coordinate.
• Type 2: Check if a block of a given size can fit entirely within a range [0, x] without intersecting any obstacles (touching is allowed).

The solution uses a segment tree to maintain the largest gap starting at each position between obstacles, and a sorted list of obstacles to efficiently update and query gaps. It answers each query in O(log n) time.

Approach:

• Segment tree stores, for each position i, the size of the gap starting at i (i.e., the distance to the next obstacle to the right).
• Obstacles list is kept sorted to allow binary search for predecessor and successor.
• Sentinel obstacle at 0 simplifies gap tracking.
• For type 2 queries, we first check the partial gap from the last obstacle to x. If that fits, answer is true. Otherwise, we query the segment tree for the maximum gap starting anywhere in [0, x - sz].
• For type 1 queries, we find predecessor and successor obstacles, update the gaps for both ends, and insert the new obstacle into the sorted list.

Let's implement this solution in PHP: 3161. Block Placement Queries

<?php
/**
 * @param Integer[][] $queries
 * @return Boolean[]
 */
function getResults(array $queries): array
{
    ...
    ...
    ...
    /**
     * go to ./solution.php
     */
}

// Test cases
echo getResults([[1,2],[2,3,3],[2,3,1],[2,2,2]]) . "\n";                // Output: [false,true,true]
echo getResults([[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]) . "\n";          // Output: [true,true,false]
?>

Explanation:

• Initialization: Start with obstacle at 0 and a large initial gap from 0 to maxVal (an upper bound slightly larger than any given coordinate).
• Type 1 (add obstacle at p):
  • Find predecessor L and successor R using binary search on sorted obstacles list.
  • Update segment tree at L with new gap p - L.
  • Update segment tree at p with new gap R - p.
  • Insert p into sorted obstacles.
• Type 2 (query for sz in [0, x]):
  • If sz > x, immediately return false.
  • Find last obstacle lastObs ≤ x using binary search.
  • If x - lastObs ≥ sz, return true (fits in rightmost gap).
  • Otherwise, query segment tree for max gap in [0, x - sz]. If that max gap ≥ sz, return true, else false.
• Segment tree operations:
  • set(idx, val) updates position idx with new gap size.
  • max(l, r) returns largest gap size in range [l, r].

Complexity

• Time Complexity:
  • Type 1: Binary search + segment tree updates → O(log n)
  • Type 2: Binary search + segment tree query → O(log n)
  • Total: O(q log n) where q is number of queries, n is range size.
• Space Complexity:
  • Segment tree: O(n)
  • Obstacles list: O(q)
  • Total: O(n + q) where n = maxVal.

Contact Links

If you found this series helpful, please consider giving the repository a star on GitHub or sharing the post on your favorite social networks 😍. Your support would mean a lot to me!

If you want more helpful content like this, feel free to follow me:

• LinkedIn
• GitHub