Detect Overlaps on 2D Grid | Dataford Interview Questions

Implement an algorithm to detect overlapping regions or annotations on a 2D grid.

Represent each annotation as [id, top, left, bottom, right], where rectangle boundaries are inclusive. Return every pair of IDs whose rectangles share at least one grid cell, sorted lexicographically. Implement detect_overlaps(annotations), returning a list of ID pairs; annotations have unique IDs and valid coordinates.

Constraints

0 <= annotations.length <= 2000
Each annotation has the form [id, top, left, bottom, right]
Annotation IDs are unique integers
top <= bottom and left <= right
Coordinates are integers in the range [-10^9, 10^9]

Function Signature

def detect_overlaps(annotations):

Your question is Detect Overlaps on 2D Grid. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.

Problem

Implement an algorithm to detect overlapping regions or annotations on a 2D grid.

Constraints

0 <= annotations.length <= 2000
Each annotation has the form [id, top, left, bottom, right]
Annotation IDs are unique integers
top <= bottom and left <= right
Coordinates are integers in the range [-10^9, 10^9]

Function Signature

def detect_overlaps(annotations):

Your question is Detect Overlaps on 2D Grid. Start with the requirements in the Question tab.

Run and submit as often as you like. When you're ready, talk me through your approach or go straight to the code.