Block Placement Queries

• Maintain a simple list of all obstacle positions.
• For a type 1 query [1, pos], add pos to the list of obstacles.
• For a type 2 query [2, x, sz]:
  1. Create a temporary list of relevant points, initially containing 0.
  2. Iterate through all obstacles placed so far. Add any obstacle with position <= x to this temporary list.
  3. Sort the temporary list.
  4. Iterate through the sorted list to find the maximum gap between consecutive points. Let the sorted points be p_0, p_1, ..., p_k. The gaps are p_1 - p_0, p_2 - p_1, ..., p_k - p_{k-1}.
  5. Also, calculate the gap from the last point p_k to x, which is x - p_k.
  6. The largest possible block size is the maximum of all these calculated gaps.
  7. Compare this maximum size with sz to determine if the block can be placed.

We use a standard List to store the positions of all obstacles as they are added. When a type 1 query [1, pos] arrives, we simply append pos to our list.

For a type 2 query [2, x, sz], we need to determine the largest contiguous empty space within the [0, x] interval. To do this, we first construct a new list containing 0 and all obstacle positions from our main list that are less than or equal to x. We then sort this new list to get an ordered set of points that define the boundaries of available segments. The largest gap is found by calculating the difference between each pair of consecutive points in the sorted list, and also the difference between x and the last point. The maximum of these values gives the size of the largest block that can be placed. If this size is at least sz, the query result is true.

1import java.util.ArrayList;2import java.util.Collections;3import java.util.List;4 5class Solution {6    public List<Boolean> getResults(int[][] queries) {7        List<Integer> obstacles = new ArrayList<>();8        List<Boolean> results = new ArrayList<>();9        for (int[] query : queries) {10            if (query[0] == 1) {11                obstacles.add(query[1]);12            } else {13                int x = query[1];14                int sz = query[2];15                16                List<Integer> currentPoints = new ArrayList<>();17                currentPoints.add(0);18                for (int obs : obstacles) {19                    if (obs <= x) {20                        currentPoints.add(obs);21                    }22                }23                24                Collections.sort(currentPoints);25                26                int maxGap = 0;27                for (int i = 1; i < currentPoints.size(); i++) {28                    maxGap = Math.max(maxGap, currentPoints.get(i) - currentPoints.get(i - 1));29                }30                maxGap = Math.max(maxGap, x - currentPoints.get(currentPoints.size() - 1));31                32                results.add(maxGap >= sz);33            }34        }35        return results;36    }37}

• Use a TreeSet to store obstacle positions, which keeps them sorted automatically.
• For a type 1 query [1, pos], add pos to the TreeSet.
• For a type 2 query [2, x, sz]:
  1. Initialize max_gap = 0 and last_pos = 0.
  2. Iterate through the obstacles in the TreeSet that are less than or equal to x. This can be done efficiently using TreeSet.headSet(x, true).
  3. For each obstacle obs, calculate the gap obs - last_pos and update max_gap. Then, set last_pos = obs.
  4. After the loop, calculate the final gap from the last obstacle to x, which is x - last_pos, and update max_gap.
  5. Compare max_gap with sz for the result.

By storing obstacle positions in a TreeSet, we ensure they are always kept in sorted order. A type 1 query [1, pos] becomes a simple add operation on the TreeSet, which takes logarithmic time.

For a type 2 query [2, x, sz], we can find the maximum gap more efficiently than the brute-force approach. We iterate through the obstacles in the TreeSet that are at or before position x. We can get a view of this subset of obstacles using headSet(x, true). We traverse these obstacles, keeping track of the previous position (last_pos, initialized to 0) to calculate the gap size. The maximum gap found during this iteration is recorded. Finally, we account for the gap between the last relevant obstacle and x. The overall maximum gap is then compared to sz.

1import java.util.ArrayList;2import java.util.List;3import java.util.TreeSet;4 5class Solution {6    public List<Boolean> getResults(int[][] queries) {7        TreeSet<Integer> obstacles = new TreeSet<>();8        List<Boolean> results = new ArrayList<>();9        10        for (int[] query : queries) {11            if (query[0] == 1) {12                obstacles.add(query[1]);13            } else {14                int x = query[1];15                int sz = query[2];16                17                int maxGap = 0;18                int lastPos = 0;19                20                // Add 0 to the set for calculation, but it's implicitly handled by lastPos=021                for (int obs : obstacles.headSet(x, true)) {22                    maxGap = Math.max(maxGap, obs - lastPos);23                    lastPos = obs;24                }25                26                maxGap = Math.max(maxGap, x - lastPos);27                28                results.add(maxGap >= sz);29            }30        }31        return results;32    }33}

• Use a Segment Tree data structure built over the range of possible coordinates [0, M], where M is the maximum coordinate value from the input.
• The segment tree will store the maximum gap length. Specifically, at leaf index p, we store the length of the gap that ends at position p.
• Use a TreeSet to maintain the sorted positions of obstacles.
• Type 1 Query [1, p]: When adding an obstacle p, it splits an existing gap. Find its neighbors prev_obs and next_obs from the TreeSet. The gap (prev_obs, next_obs) is replaced by (prev_obs, p) and (p, next_obs). Update the segment tree: set the value at index p to p - prev_obs and the value at index next_obs to next_obs - p. Then add p to the TreeSet.
• Type 2 Query [2, x, sz]: The maximum block size is the larger of two values:
  1. The maximum gap between any two consecutive obstacles both located at or before x. This is found by querying the segment tree for the maximum value in the range [0, x].
  2. The gap from the last obstacle before x to x itself. This is found using TreeSet.floor(x).
• Compare the result with sz.

To solve this problem efficiently, we need to quickly answer the question: 'What is the largest available space in [0, x]?'. This space is determined by the maximum of two quantities: 1) the largest gap between two consecutive obstacles within [0, x], and 2) the gap from the last obstacle in [0, x] to x.

A TreeSet helps us find the last obstacle and its neighbors efficiently. A segment tree helps us find the maximum internal gap. We build the segment tree over the coordinate space. Each leaf i of the tree stores the length of the gap that ends at position i. An internal node stores the maximum gap length in its corresponding range.

When an obstacle at p is added (Type 1), it splits a gap (prev, next). We update our segment tree by changing the gap lengths associated with endpoints p and next. This is a point update operation, which is O(log M).

When we check for placing a block (Type 2), we query the segment tree for the maximum value in [0, x] to get the largest internal gap. This is a range query, also O(log M). We also find the gap to x using the TreeSet in O(log Q_1). The maximum of these two values gives us our answer.

1import java.util.ArrayList;2import java.util.List;3import java.util.TreeSet;4 5class SegmentTree {6    private int[] tree;7    private int n;8 9    public SegmentTree(int size) {10        this.n = size;11        this.tree = new int[4 * n];12    }13 14    public void update(int node, int start, int end, int idx, int val) {15        if (start == end) {16            tree[node] = val;17            return;18        }19        int mid = start + (end - start) / 2;20        if (start <= idx && idx <= mid) {21            update(2 * node + 1, start, mid, idx, val);22        } else {23            update(2 * node + 2, mid + 1, end, idx, val);24        }25        tree[node] = Math.max(tree[2 * node + 1], tree[2 * node + 2]);26    }27 28    public int query(int node, int start, int end, int l, int r) {29        if (r < start || end < l || l > r) {30            return 0;31        }32        if (l <= start && end <= r) {33            return tree[node];34        }35        int mid = start + (end - start) / 2;36        int p1 = query(2 * node + 1, start, mid, l, r);37        int p2 = query(2 * node + 2, mid + 1, end, l, r);38        return Math.max(p1, p2);39    }40}41 42class Solution {43    public List<Boolean> getResults(int[][] queries) {44        int maxCoord = 0;45        for (int[] q : queries) {46            maxCoord = Math.max(maxCoord, q[1]);47        }48        maxCoord++;49 50        SegmentTree st = new SegmentTree(maxCoord);51        TreeSet<Integer> obstacles = new TreeSet<>();52        obstacles.add(0);53        54        List<Boolean> results = new ArrayList<>();55 56        for (int[] query : queries) {57            if (query[0] == 1) {58                int p = query[1];59                Integer prev = obstacles.floor(p);60                Integer next = obstacles.ceiling(p);61 62                if (next != null) {63                    st.update(0, 0, maxCoord - 1, next, next - p);64                }65                st.update(0, 0, maxCoord - 1, p, p - prev);66                67                obstacles.add(p);68            } else {69                int x = query[1];70                int sz = query[2];71 72                int maxInternalGap = st.query(0, 0, maxCoord - 1, 0, x);73                74                Integer lastObs = obstacles.floor(x);75                int gapToX = x - lastObs;76 77                results.add(Math.max(maxInternalGap, gapToX) >= sz);78            }79        }80        return results;81    }82}