LeetCode 3161 - Block Placement Queries

The problem involves simulating operations on an infinite number line starting at 0 and extending towards the positive x-axis.

leetcodehardarraybinary-searchbinary-indexed-treesegment-tree

LeetCode Problem 3161

Difficulty: 🔴 Hard
Topics: Array, Binary Search, Binary Indexed Tree, Segment Tree

Solution

Problem Understanding

The problem involves simulating operations on an infinite number line starting at 0 and extending towards the positive x-axis. There are two types of queries: placing obstacles at certain points, and checking whether a block of a given size can fit anywhere in the range [0, x] without overlapping any obstacles. A block can touch an obstacle but cannot intersect it.

The input is a 2D array queries. For queries of type 1 ([1, x]), we record that an obstacle exists at x. For queries of type 2 ([2, x, sz]), we must determine if it is possible to place a block of size sz entirely within [0, x] without overlapping any existing obstacles. The output is a boolean array corresponding to the type 2 queries.

Constraints indicate that queries.length can go up to about 150,000, and obstacle positions and block sizes are capped at roughly 150,000 as well. This rules out naive brute-force approaches that iterate over the line directly, as the time and memory complexity would be too high. The problem guarantees no duplicate obstacle placements and at least one type 2 query, which ensures we always produce some output.

Edge cases to consider include queries where the block size exactly matches the distance to the nearest obstacle, multiple obstacles clustered together, or checking for placement when no obstacles exist.

Approaches

Brute Force

A brute-force approach would maintain a sorted list of obstacles and, for each type 2 query, iterate through all segments of [0, x] between obstacles to see if there is enough contiguous space to fit the block. This is correct but inefficient: each type 2 query may require O(n) operations, where n is the number of obstacles already placed. For up to 150,000 queries, this would be prohibitively slow.

Optimal Approach

The key observation is that each type 2 query reduces to finding whether there exists a gap of size at least sz between consecutive obstacles (or between 0 and the first obstacle) in the range [0, x]. If we maintain the obstacle positions in a sorted data structure like a balanced binary search tree or SortedList in Python, we can efficiently locate the next obstacle after any given position. This allows us to quickly check available gaps for each query.

The optimal solution uses a sorted set of obstacle positions and for each type 2 query, it checks the largest available gaps within [0, x] without scanning all positions. This reduces the complexity from potentially O(n^2) to O(n log n).

Approach Time Complexity Space Complexity Notes
Brute Force O(n^2) O(n) Check all gaps for each query explicitly
Optimal O(n log n) O(n) Maintain sorted obstacles, binary search to find gaps

Algorithm Walkthrough

  1. Initialize a sorted set of obstacles. Start with 0 as a virtual obstacle to simplify gap calculations.
  2. Iterate through each query:
  3. If the query is type 1, insert the obstacle position into the sorted set.
  4. If the query is type 2 with parameters [2, x, sz]:

a. Find the first obstacle greater than x using binary search in the sorted set.

b. Consider all gaps between consecutive obstacles starting from 0 up to x.

c. For each gap, calculate gap_size = next_obstacle - prev_obstacle. If gap_size >= sz, mark this query as True and stop checking further.

d. If no gap is large enough, mark the query as False. 5. Return the results for all type 2 queries.

Why it works: By maintaining obstacles in a sorted set, we guarantee that all gaps between obstacles are considered in ascending order of position. This ensures no potential placement is missed, and checking only gaps between consecutive obstacles suffices because a block cannot overlap obstacles.

Python Solution

from typing import List
from sortedcontainers import SortedList

class Solution:
    def getResults(self, queries: List[List[int]]) -> List[bool]:
        obstacles = SortedList()
        results = []
        for query in queries:
            if query[0] == 1:
                obstacles.add(query[1])
            else:
                x, sz = query[1], query[2]
                idx = obstacles.bisect_right(x)
                prev = 0
                can_place = False
                # Check gaps between 0 and x using obstacles up to x
                for i in range(idx):
                    curr = obstacles[i]
                    if curr - prev >= sz:
                        can_place = True
                        break
                    prev = curr
                if not can_place:
                    # Check the last gap from last obstacle to x
                    if x - prev >= sz:
                        can_place = True
                results.append(can_place)
        return results

The implementation uses SortedList from the sortedcontainers library to maintain a sorted set of obstacles with efficient O(log n) insertion and binary search. For each type 2 query, we only iterate over obstacles up to x, checking gaps sequentially.

Go Solution

package main

import (
	"sort"
)

func getResults(queries [][]int) []bool {
	obstacles := []int{}
	results := []bool{}
	for _, query := range queries {
		if query[0] == 1 {
			x := query[1]
			pos := sort.SearchInts(obstacles, x)
			obstacles = append(obstacles, 0)
			copy(obstacles[pos+1:], obstacles[pos:])
			obstacles[pos] = x
		} else {
			x, sz := query[1], query[2]
			idx := sort.Search(len(obstacles), func(i int) bool { return obstacles[i] > x })
			prev := 0
			canPlace := false
			for i := 0; i < idx; i++ {
				curr := obstacles[i]
				if curr-prev >= sz {
					canPlace = true
					break
				}
				prev = curr
			}
			if !canPlace && x-prev >= sz {
				canPlace = true
			}
			results = append(results, canPlace)
		}
	}
	return results
}

In Go, we maintain a sorted slice manually. Insertions require shifting elements, and sort.SearchInts is used for binary search. This achieves the same logic as Python with O(n log n) complexity.

Worked Examples

Example 1: queries = [[1,2],[2,3,3],[2,3,1],[2,2,2]]

Step Obstacles Query Action Result
1 [] [1,2] Add obstacle at 2 [2]
2 [2] [2,3,3] Gaps: 0-2=2, 2-3=1; block 3 cannot fit false
3 [2] [2,3,1] Gap 0-2=2 >=1; block fits true
4 [2] [2,2,2] Gap 0-2=2 >=2; block fits true

Output: [false, true, true]

Example 2: queries = [[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]

Step Obstacles Query Action Result
1 [] [1,7] Add 7 [7]
2 [7] [2,7,6] Gap 0-7=7 >=6; block fits true
3 [7] [1,2] Add 2 [2,7]
4 [2,7] [2,7,5] Gaps: 0-2=2, 2-7=5 >=5; fits true
5 [2,7] [2,7,6] Gaps: 0-2=2, 2-7=5<6; cannot fit false

Output: [true,true,false]

Complexity Analysis

Measure Complexity Explanation
Time O(n log n) Insertion and search in a sorted set cost O(log n) per operation, n queries total
Space O(n) Storing all obstacles in a sorted set

The main work is maintaining sorted obstacles and checking gaps. Each type 2 query only inspects obstacles up to x, which is at most n obstacles.

Test Cases

# Provided examples
assert Solution().getResults([[1,2],[2,3,3],[2,3,1],[2,2,2]]) == [False, True, True]
assert Solution().getResults([[1,7],[2,7,6],[1,2],[2,7,5],[2,7,6]]) == [True, True, False]

# Edge cases
assert Solution().getResults([[2,5,3]]) == [True]  # No obstacles
assert Solution().getResults([[1,1],[2,1,1]]) == [False]  # Block exactly at obstacle