Count queen attacks on points with blockers

Q: Count queen attacks on points with blockers

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.

Q: How do I approach Coding & Algorithms interview questions?

Coding & Algorithms questions require understanding of core concepts and practice. PracHub provides solutions with explanations to help you master coding & algorithms interviews.

Question

You are given positions on an (unbounded) 2D integer grid.

queens : coordinates of queens
points : query coordinates

A queen attacks along 8 directions: horizontal, vertical, and the two diagonals.

Part 1 — No blockers

For each point p in points, compute how many queens can attack p.

A queen at q attacks p if p lies on the same row, column, or diagonal as q .

Return an array ans where ans[i] is the number of queens attacking points[i].

Part 2 — Blockers (rocks)

Now you are also given:

rocks : coordinates of rocks

Rocks block attacks. A queen attacks a point p only if, along the line from the queen to p, there is no rock strictly between them.

Again return ans[i] for each query point.

Input/Output

Input: queens , points , and optionally rocks
Output: integer array of size len(points)

Constraints (reasonable interview constraints)

1 <= len(queens), len(points), len(rocks) <= 2*10^5
Coordinates fit in 32-bit signed integers.
Aim for about O((Q + R + P) log(Q+R)) time for Part 2.

Count queen attacks on points with blockers

Quick Overview

Part 1 — No blockers

Part 2 — Blockers (rocks)

Input/Output

Constraints (reasonable interview constraints)

Comments (0)