Block Placement Queries
Source: leetcode
Difficulty: Hard
Tags: array, binary-search, binary-indexed-tree, segment-tree

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:**


**![](https://assets.leetcode.com/uploads/2024/04/22/example0block.png)**


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:**


**![](https://assets.leetcode.com/uploads/2024/04/22/example1block.png)**


- 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\.




C++ solution:
struct node
{
    int sz;
    int big;
    int left;
    int right;
};

class Segtree {
public:
    int n;
    bool* arr;
    int chunksize;
    node* blocks;

    Segtree(uint32_t n)
    {
        this -> n = n;
        this -> chunksize = sqrt(n)+1;
        this -> arr = (bool *) calloc(n + 3 + chunksize, sizeof(bool));
        this -> blocks = (node *)malloc((chunksize+2)*sizeof(node));
        for (int it = 0, at = 0; at <= n; it++, at += chunksize)
            blocks[it] = {chunksize, chunksize, chunksize, chunksize};
    }

    node coalesce(node levo, node desno)
    {
        node comb;
        comb.sz = levo.sz + desno.sz;
        if (levo.sz == levo.big and desno.sz == desno.big)
        {
            // both completely empty.
            comb.big = comb.sz;
            comb.left = comb.big;
            comb.right = comb.big;
        }
        else if (levo.sz == levo.big)
        {
            // left completely empty
            comb.big = max(desno.big, levo.sz + desno.left);
            comb.left = levo.sz + desno.left;
            comb.right = desno.right;
        }
        else if (desno.sz == desno.big)
        {
            // right completely empty
            comb.big = max(levo.big, levo.right + desno.sz);
            comb.right = levo.right + desno.sz;
            comb.left = levo.left;
        }
        else 
        {
            // both have blocks.
            comb.big = max(levo.big, levo.right + desno.left);
            comb.big = max(comb.big, desno.big);
            comb.left = levo.left;
            comb.right = desno.right;
        }
        return comb;
    }
    
    node compute(int left, int right)
    {
        int st = left;
        while (!arr[st] and st < right)
            st++;

        int end = right;
        while (end >= 0 and !arr[end])
            end--;

        node block;
        block.sz = right - left + 1;
        block.left = st - left;
        block.right = right - end;
        int cons = 0;
        int mx = 0;
        for (int i = left; i <= right; i++)
        {
            if (!arr[i])
                mx = max(mx, ++cons);
            else
                cons = 0;
        }
        block.big = mx;
        return block;
    }

    void update(int pos)
    {
        arr[pos] = 1;
        int it = 0, at = 0;
        while (at <= n)
        {
            if (at <= pos and pos < at + chunksize)
            {
                blocks[it] = compute(at, at + chunksize - 1);
                break;
            }
            it++;
            at += chunksize;
        }
    }

    int query(int lrange, int rrange)
    {
        if (rrange - lrange <= chunksize)
        {
            node cur = compute(lrange, rrange);
            return cur.big;
        }

        int it = 0, at = 0;
        node cur = {0, 0, 0, 0};
        while (at <= rrange)
        {
            if (lrange <= at and at + chunksize - 1 <= rrange) // entirely inside.
                cur = coalesce(cur, blocks[it]); 
            else if (at < lrange and lrange < at + chunksize) // leftmost block partly inside.
                cur = coalesce(cur, compute(lrange, at + chunksize - 1));
            else if (at <= rrange and rrange < at + chunksize - 1)  // rightmost block partly inside.
                cur = coalesce(cur, compute(at, rrange));
            it++;
            at += chunksize;
        }
        return cur.big;
    }

    void printblock (node block)
    {
        cout<<block.sz<<" "<<block.big<<" "<<block.left<<" "<<block.right<<"\n";
    }

};

class Solution {
public:
    vector<bool> getResults(vector<vector<int>>& queries) {
        Segtree object(queries.size() * 3 + 1);
        vector <bool> results;
        for (vector <int> & query : queries)
        {
            if (query[0] == 1)
            {
                object.update(query[1]);
            }
            else 
            {
                int x = query[1];
                int sz = query[2];
                results.push_back(object.query(1, x-1) + 1 >= sz);
            }
        }
        return results;
    }
};

Go solution:
func getResults(queries [][]int) []bool {
	obs := make([]int, 0, 1<<5)
	res := make([]bool, 0, len(queries))
	st := NewSegmentTreeWithMap[int](5*1e4)
	for _, q := range queries {
		idx, _ := slices.BinarySearch(obs, q[1])
		switch q[0] {
		case 1: // place obs
			obs = slices.Insert(obs, idx, q[1])
			prevObs := 0
			if idx > 0 {
				prevObs = obs[idx-1]
			}
			st.Update(obs[idx], obs[idx]-prevObs)
			if idx < len(obs)-1 {
				st.Update(obs[idx+1], obs[idx+1]-obs[idx])
			}
		case 2:
			maxGap := q[1]
			if idx > 0 {
				maxGap = max(q[1]-obs[idx-1], st.Query(0, obs[idx-1]))
			}
			res = append(res, maxGap >= q[2])
		}
	}
	return res
}

type segmentTreeWithMap[T ~int] struct {
	data             map[int]T
	size             int
}

type SegmentTree[T ~int] interface {
	Query(lo, hi int) T
	Update(pos int, val T)
}

func NewSegmentTreeWithMap[T ~int](size int) SegmentTree[T] {
	return &segmentTreeWithMap[T]{
		data:             make(map[int]T),
		size:             size,
	}
}

func (st *segmentTreeWithMap[T]) Query(lo, hi int) T {
	lo += st.size
	hi += st.size
	res := st.data[hi]
	for lo < hi {
		if lo&1 != 0 {
			res = max(res, st.data[lo])
			lo++
		}
		if hi&1 != 0 {
			hi--
			res = max(res, st.data[hi])
		}
		lo >>= 1
		hi >>= 1
	}
	return res
}

func (st *segmentTreeWithMap[T]) Update(pos int, val T) {
	pos += st.size
	st.data[pos] = val
	for pos > 1 {
		pos >>= 1
		st.data[pos] = max(st.data[2*pos], st.data[2*pos+1])
	}
}

Java solution:
class Solution {

    static int dist[];
    static int ans[];
    static ArrayList<Integer> obstacle;

    // Segment Tree

    static void buildTree(int l, int r, int idx){
        if(l==r){
            ans[idx] = dist[l];
            return;
        }

        int mid = l+(r-l)/2;
        buildTree(l,mid,2*idx+1);
        buildTree(mid+1,r,2*idx+2);
        ans[idx] = Math.max(ans[2*idx+1],ans[2*idx+2]);
    }

    static int findMax(int l, int r, int left, int right, int idx){
        if(r<left || l>right) return Integer.MIN_VALUE;
        if(l>=left && r<=right) return ans[idx];

        int mid = l+(r-l)/2;
        int a = findMax(l,mid,left,right,2*idx+1);
        int b = findMax(mid+1,r,left,right,2*idx+2);
        return Math.max(a,b);
    }

    static void update(int l, int r, int idx, int pos, int val){
        if(l==r){
            ans[idx] = val;
            return;
        }

        int mid = l+(r-l)/2;
        if(pos<=mid) update(l,mid,2*idx+1,pos,val);
        else update(mid+1,r,2*idx+2,pos,val);
        ans[idx] = Math.max(ans[2*idx+1],ans[2*idx+2]);
    }

    // finding Next and Prev Obstacle

    public static int findNext(int x) {
        int left = 0;
        int right = obstacle.size() - 1;
        int result = -1; 

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (obstacle.get(mid) > x) {
                result = mid; 
                right = mid - 1; 
            } else {
                left = mid + 1; 
            }
        }
        return result;
    }

    public static int findPrev(int x) {
        int left = 0;
        int right = obstacle.size() - 1;
        int result = -1; 

        while (left <= right) {
            int mid = left + (right - left) / 2;

            if (obstacle.get(mid) < x) {
                result = mid;
                left = mid + 1; 
            } else {
                right = mid - 1; 
            }
        }
        return result;
    }

    // Actual code

    public static List<Boolean> getResults(int[][] q){

        int n = Math.min(50004,3*q.length)+5;

        dist = new int[n];
        ans = new int[4*n];
        obstacle = new ArrayList<>();
        obstacle.add(0);
        obstacle.add(n-1);
        List<Boolean> a = new ArrayList<>();
        dist[n-1] = n-1;
        buildTree(0,n-1,0);

        boolean flag = true;

        for(int i=0; i<q.length; i++){
            int type = q[i][0];
            int x = q[i][1];
            if(type==1){
                flag = false;

                int nx = findNext(x);
                int pr = findPrev(x);

                int next = obstacle.get(nx);
                int prev = obstacle.get(pr);
                obstacle.add(nx,x);

                dist[x] = x-prev;
                update(0,n-1,0,x,x-prev);
                dist[next] = next-x;
                update(0,n-1,0,next,next-x);

            }else{
                int sz = q[i][2];
                int prev = findPrev(x);
                int max = findMax(0,n-1,0,obstacle.get(prev),0);
                max = Math.max(max,x-obstacle.get(prev));

                if(flag) max = x-obstacle.get(prev);

                if(sz<=max) a.add(true);
                else a.add(false);
            }

        }
        return a;
    }

    public static void main(String[] args) {
        int q[][] = {{2,3,1}};
        System.out.println(getResults(q));
    }
}

JavaScript solution:
/**
 * @param {number[][]} queries
 * @return {boolean[]}
 */
var getResults = function (queries) {
    let main = [];
    let larg = [];
    let ans = [];

    for (const q of queries) {
        if (q[0] === 1) {
            let ind = bisect(main, q[1]);

            if (ind === 0) {
                main.splice(0, 0, q[1]);
                larg.splice(0, 0, q[1]);
            } else {
                main.splice(ind, 0, q[1]);
                larg.splice(ind, 0, Math.max(larg[ind - 1], (main[ind] - main[ind - 1])));
            }

            ind += 1;

            while (ind < main.length) {
                if (larg[ind] === larg[ind - 1]) {
                    break;
                }
                larg[ind] = Math.max(larg[ind - 1], (main[ind] - main[ind - 1]));
                ind += 1;
            }
        } else {
            if (q[2] > q[1]) {
                ans.push(false);
            } else {
                let ind = bisect(main, q[1]);
                let lim;

                if (ind === 0) {
                    lim = q[1];
                } else if (main[ind - 1] === q[1]) {
                    lim = larg[ind - 1];
                } else {
                    lim = Math.max(larg[ind - 1], (q[1] - main[ind - 1]));
                }

                ans.push(q[2] <= lim);
            }
        }
    }

    return ans;
};

// Helper function to simulate bisect_left from Python's bisect module
function bisect(arr, x) {
    let left = 0;
    let right = arr.length;

    while (left < right) {
        let mid = Math.floor((left + right) / 2);

        if (arr[mid] < x) {
            left = mid + 1;
        } else {
            right = mid;
        }
    }

    return left;
}

Python solution:
class Solution:
    def getResults(self, queries: List[List[int]]) -> List[bool]:
        def bsearch(l, v):
            b = -1
            e = len(l)
            while e - b > 1:
                m = (b + e) // 2
                if l[m] >= v:
                    e = m
                if l[m] <= v:
                    b = m
            return b, e
        l = [0]
        a = []
        for q in queries:
            if q[0] == 1:
                l.append(q[1])
            else:
                a.append(True)
        l = sorted(l)
        p = len(a)
        m = 0
        sw = []
        sv = []
        for i in range(len(l) - 1):
            w = l[i + 1] - l[i]
            if w > m:
                sw.append(w)
                sv.append(l[i])
                m = w
        n = len(queries)
        # print(l, sv, sw)
        for j in range(len(queries)):
            q = queries[n - 1 - j]
            if q[0] == 1:
                v = q[1]
                i, i = bsearch(l, v)
                vb, ve = bsearch(sv, l[i - 1])
                if i < len(l) - 1:
                    w = l[i + 1] - l[i - 1]
                    wb, we = bsearch(sw, w)
                    # if wb == 7 and w == 12:
                    #     print(v, i, vb, ve, sv)
                    #     print('---', wb, we, sw)
                    del sw[ve: wb + 1]
                    del sv[ve: wb + 1]
                    if vb < wb or vb == wb and ve <= we:
                        sw.insert(ve, w)
                        sv.insert(ve, l[i - 1])
                elif vb == ve:
                    del sw[ve]
                    del sv[ve]
                del l[i]
            else:
                p -= 1
                v = q[1]
                w = q[2]
                ib, ie = bsearch(sw, w)
                # if p == 23272:
                    # print('====================', v, w, ib, ie, sv, sw)
                if ie == len(sw):
                    a[p] = v - w >= l[-1]
                else:
                    a[p] = v - w >= sv[ie]
        return a

Ruby solution:
def get_results(queries)
    obstacles = []
    max_gaps = []
    results = []

    queries.each do |q|
        if q[0] == 1
            # Insert obstacle
            x = q[1]
            idx = obstacles.bsearch_index { |o| o >= x } || obstacles.size
            obstacles.insert(idx, x)

            prev_obstacle = idx > 0 ? obstacles[idx - 1] : 0
            new_gap = x - prev_obstacle

            new_max = if idx == 0
                        new_gap
                      else
                        [max_gaps[idx - 1], new_gap].max
                      end

            # Insert new_max into max_gaps
            max_gaps.insert(idx, new_max)

            # Propagate to the right
            i = idx + 1
            while i < obstacles.size
                prev_gap = obstacles[i] - obstacles[i - 1]
                current_max = [max_gaps[i - 1], prev_gap].max
                if current_max == max_gaps[i]
                    break
                else
                    max_gaps[i] = current_max
                    i += 1
                end
            end
        else
            # Check block placement
            x = q[1]
            sz = q[2]
            if obstacles.empty?
                results << (x >= sz)
                next
            end

            idx = obstacles.bsearch_index { |o| o > x }
            prev_idx = idx ? idx - 1 : obstacles.size - 1

            if prev_idx < 0
                max_gap = x
            else
                prev_obstacle = obstacles[prev_idx]
                max_gap_up_to_prev = max_gaps[prev_idx]
                gap_from_prev = x - prev_obstacle
                max_gap = [max_gap_up_to_prev, gap_from_prev].max
            end

            results << (max_gap >= sz)
        end
    end

    results
end