3161. Block Placement Queries

Description

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:

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

 

Solutions

Solution: Binary Indexed Tree + Binary Search

• Time complexity: O(10⁵+nlog10⁵)
• Space complexity: O(10⁵+queries.length)

 

JavaScript

/**
 * @param {number[][]} queries
 * @return {boolean[]}
 */
const getResults = function (queries) {
  const n = queries.length;
  const maxNum = Math.min(50000, n * 3);
  const result = [];
  const tree = new BIT(maxNum);
  const obstacles = new OrderedSet();

  obstacles.insert(0);
  obstacles.insert(maxNum);

  for (const [type, x] of queries) {
    if (type === 1) {
      obstacles.insert(x);
    }
  }

  for (let index = 1; index < obstacles.arr.length; index++) {
    const prev = obstacles.arr[index - 1];
    const current = obstacles.arr[index];

    tree.maximize(current, current - prev);
  }

  for (let index = n - 1; index >= 0; index--) {
    const [type, x, sz] = queries[index];

    if (type === 1) {
      const obstacle = obstacles.findIndex(x);

      if (obstacle !== -1 && obstacle + 1 < obstacles.arr.length) {
        const prevX = obstacles.arr[obstacle - 1];
        const nextX = obstacles.arr[obstacle + 1];

        tree.maximize(nextX, nextX - prevX);
      }

      obstacles.erase(x);
    } else {
      const upper = obstacles.upperBoundIndex(x);
      const prev = obstacles.arr[upper - 1];
      const isPlacement = x - prev >= sz || tree.query(prev) >= sz;

      result.push(isPlacement);
    }
  }

  return result.toReversed();
};

class BIT {
  constructor(n) {
    this.bit = Array.from({ length: n + 2 }, () => 0);
  }

  maximize(x, delta) {
    while (x < this.bit.length) {
      this.bit[x] = Math.max(this.bit[x], delta);
      x += x & -x;
    }
  }

  query(x) {
    let result = 0;

    while (x) {
      result = Math.max(this.bit[x], result);
      x -= x & -x;
    }

    return result;
  }
}

class OrderedSet {
  arr = [];

  upperBoundIndex(val) {
    let left = 0;
    let right = this.arr.length - 1;

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

      this.arr[mid] > val ? (right = mid - 1) : (left = mid + 1);
    }

    return left;
  }

  insert(val) {
    const index = this.upperBoundIndex(val);

    if (index > 0 && this.arr[index - 1] === val) return;

    this.arr.splice(index, 0, val);
  }

  erase(val) {
    const index = this.upperBoundIndex(val) - 1;

    if (index >= 0 && this.arr[index] === val) {
      this.arr.splice(index, 1);
    }
  }

  findIndex(val) {
    const index = this.upperBoundIndex(val) - 1;

    return index >= 0 && this.arr[index] === val ? index : -1;
  }
}