Count queen attacks on points with blockers
Company: Voleon
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: nan
Interview Round: Technical Screen
Quick Answer: This question evaluates spatial reasoning on an integer 2D grid, geometric line relationships for queens' attack paths, and the use of efficient data structures to count interactions and handle occlusion, in the Coding & Algorithms domain.
Part 1: Count Queen Attacks Without Blockers
Constraints
- 0 <= len(queens) <= 2 * 10^5
- 0 <= len(points) <= 2 * 10^5
- Coordinates fit in 32-bit signed integers.
- Query points may repeat.
- If a queen is exactly on a query point, that queen does not count as attacking that point.
Examples
Input: ([[0, 0], [1, 2], [3, 0], [2, 2]], [[0, 2], [2, 0], [1, 1], [5, 5]])
Expected Output: [3, 3, 3, 2]
Explanation: For example, [0, 2] is attacked by two queens on row y=2 and one queen on column x=0.
Input: ([], [[0, 0], [1, 1]])
Expected Output: [0, 0]
Explanation: With no queens, no point is attacked.
Input: ([[2, 3]], [[2, 3], [2, 10], [10, 3], [5, 6], [5, 7]])
Expected Output: [0, 1, 1, 1, 0]
Explanation: The queen does not attack its own square, but it attacks points in the same column, row, and diagonal.
Input: ([[-1, -1], [-2, 0], [3, -3]], [[0, 0], [-2, -2], [3, 0]])
Expected Output: [3, 2, 2]
Explanation: Negative coordinates work the same way; diagonals are identified by x-y and x+y.
Solution
def solution(queens, points):
from collections import Counter
rows = Counter()
cols = Counter()
main_diags = Counter()
anti_diags = Counter()
queen_at = Counter()
for x, y in queens:
rows[y] += 1
cols[x] += 1
main_diags[x - y] += 1
anti_diags[x + y] += 1
queen_at[(x, y)] += 1
ans = []
for x, y in points:
total = rows[y] + cols[x] + main_diags[x - y] + anti_diags[x + y]
total -= 4 * queen_at[(x, y)]
ans.append(total)
return ansTime complexity: O(Q + P), where Q = len(queens) and P = len(points). Space complexity: O(Q).
Hints
- A queen can attack a point based only on four line identifiers: row, column, x - y diagonal, and x + y diagonal.
- Be careful not to count a queen on the query point itself four times.
Part 2: Count Queen Attacks With Blocking Rocks
Constraints
- 0 <= len(queens) <= 2 * 10^5
- 0 <= len(points) <= 2 * 10^5
- 0 <= len(rocks) <= 2 * 10^5
- Coordinates fit in 32-bit signed integers.
- Queens and rocks do not occupy the same coordinate.
- Query points may repeat and may coincide with a queen or a rock.
Examples
Input: ([[0, 0], [0, 3], [3, 0], [2, 2], [-2, 2]], [[0, 2], [0, -1], [1, 1], [3, 3]], [[0, 1], [1, 1], [2, 0]])
Expected Output: [3, 1, 2, 3]
Explanation: For [0,2], the rock at [0,1] blocks the queen at [0,0], but not the queen at [0,3]. The query [1,1] is itself a rock, but endpoint rocks are not strictly between.
Input: ([[0, 0], [1, 1], [2, 0]], [[1, 0], [1, 1], [3, 3]], [])
Expected Output: [3, 2, 2]
Explanation: With no rocks, this reduces to the no-blockers version.
Input: ([[0, 0], [0, 5], [5, 0], [5, 5]], [[0, 4], [4, 0], [4, 4], [1, 1]], [[0, 2], [2, 0], [3, 3]])
Expected Output: [1, 1, 1, 1]
Explanation: Each query has one visible queen on its line segment before hitting a rock.
Input: ([[2, 2], [2, 5], [5, 2], [0, 0]], [[2, 2], [2, 4]], [[2, 3], [3, 2], [1, 1]])
Expected Output: [0, 1]
Explanation: The queen at [2,2] does not attack its own square, and rocks block the other aligned queens from that square.
Input: ([[0, 0]], [], [[0, 1]])
Expected Output: []
Explanation: No query points means the answer is empty.
Solution
def solution(queens, points, rocks):
from collections import defaultdict, Counter
from bisect import bisect_left, bisect_right
queen_lines = [defaultdict(list) for _ in range(4)]
rock_lines = [defaultdict(list) for _ in range(4)]
queen_at = Counter()
def add_to_lines(lines, x, y):
lines[0][y].append(x) # row: key y, position x
lines[1][x].append(y) # column: key x, position y
lines[2][x - y].append(x) # main diagonal: key x-y, position x
lines[3][x + y].append(x) # anti-diagonal: key x+y, position x
for x, y in queens:
add_to_lines(queen_lines, x, y)
queen_at[(x, y)] += 1
for x, y in rocks:
add_to_lines(rock_lines, x, y)
for family in range(4):
for values in queen_lines[family].values():
values.sort()
for values in rock_lines[family].values():
values.sort()
def count_visible_on_line(family, key, t):
queens_on_line = queen_lines[family].get(key)
if not queens_on_line:
return 0
rocks_on_line = rock_lines[family].get(key, [])
left_rock_index = bisect_left(rocks_on_line, t) - 1
right_rock_index = bisect_right(rocks_on_line, t)
if left_rock_index >= 0:
left_bound = rocks_on_line[left_rock_index]
left = bisect_right(queens_on_line, left_bound)
else:
left = 0
if right_rock_index < len(rocks_on_line):
right_bound = rocks_on_line[right_rock_index]
right = bisect_left(queens_on_line, right_bound)
else:
right = len(queens_on_line)
return right - left
ans = []
for x, y in points:
total = 0
total += count_visible_on_line(0, y, x)
total += count_visible_on_line(1, x, y)
total += count_visible_on_line(2, x - y, x)
total += count_visible_on_line(3, x + y, x)
# A queen exactly at the query coordinate was counted once in each
# of the four line families, but it does not attack its own square.
total -= 4 * queen_at[(x, y)]
ans.append(total)
return ansTime complexity: O((Q + R) log(Q + R) + P log(Q + R)), where Q = len(queens), R = len(rocks), and P = len(points). Space complexity: O(Q + R).
Hints
- Handle each row, column, and diagonal as a separate sorted 1D line.
- For a query point on a line, only queens between the nearest rock before the point and the nearest rock after the point can attack along that line.