We use cookies (including Google cookies) to personalize ads and analyze traffic. By continuing to use our site, you accept our Privacy Policy.

SimplyLeet
TagsDisclaimersPrivacyTermsContactAbout Us

Block Placement Queries

Difficulty: Hard

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

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.

Key Insights

  • The problem involves maintaining a list of obstacles on a number line and checking the available space to place blocks.
  • Efficiently handling dynamic updates (adding obstacles) and queries (checking available space) is crucial.
  • A sorted list can help in quickly locating obstacles and determining if there is enough space to place a block.
  • Binary search can be used to efficiently find the closest obstacle within the specified range.

Space and Time Complexity

Time Complexity: O(n log n) where n is the number of queries. Each insertion and query can be done in O(log n) time due to binary search on a sorted list of obstacles. Space Complexity: O(n) for storing the obstacles.

Solution

To solve this problem, we utilize a sorted list to keep track of the positions of the obstacles. When an obstacle is added (type 1 query), it is inserted into this list while maintaining the order. For type 2 queries, we check the obstacles within the range [0, x] using binary search. The key is to find the position of the leftmost obstacle and determine if there is enough continuous space to accommodate the block of size sz.

Code Solutions

from bisect import bisect_right

def blockPlacementQueries(queries):
    obstacles = []
    results = []
    
    for query in queries:
        if query[0] == 1:
            # Add an obstacle
            x = query[1]
            obstacles.append(x)
            obstacles.sort()  # Maintain sorted order
        else:
            # Check for block placement
            x, sz = query[1], query[2]
            pos = bisect_right(obstacles, x)  # Find the rightmost obstacle <= x
            
            # Check the space before the first obstacle and after the last obstacle
            can_place = True
            
            # Check space before the first obstacle
            if pos > 0:
                if obstacles[pos - 1] >= sz:
                    can_place = False
            
            # Check space between obstacles
            for i in range(pos - 1):
                if obstacles[i + 1] - obstacles[i] < sz:
                    can_place = False
            
            # Check space after the last obstacle
            if pos < len(obstacles):
                if x - obstacles[pos - 1] < sz:
                    can_place = False
            
            results.append(can_place)
    
    return results
← Back to All Questions