Count Overlapping Pairs of 2x2 Squares Given Their Centers
Company: Ramp
Role: Software Engineer
Category: Coding & Algorithms
Difficulty: easy
Interview Round: Online Assessment
Overview: Given the integer center coordinates of axis-aligned 2x2 squares, count how many pairs overlap, where touching at an edge or a corner counts and repeated centers are allowed. It tests geometric reasoning about square intersection and counting pairs efficiently when there are up to 100,000 squares.
Constraints
- 1 <= n <= 10^5, where n is the length of centers
- Each centers[i] = [x, y] holds exactly two integers
- -10^9 <= x, y <= 10^9, and all coordinates are integers
- The answer can be as large as n * (n - 1) / 2, about 5 * 10^9, which exceeds 2^31 - 1: return a 64-bit integer (long in Java, long long in C++)
Examples
Input: ([[0, 0], [2, 0], [5, 5], [1, 1]],)
Expected Output: 3
Explanation: Source example 1: (0,0)-(2,0) touch along an edge, (1,1) overlaps both, (5,5) is isolated.
Input: ([[0, 0], [3, 0], [0, 0], [2, 2]],)
Expected Output: 4
Explanation: Source example 2: the duplicate (0,0) pair, both touch (2,2) at a corner, and (3,0) touches (2,2) along an edge.
Hints
- Two axis-aligned squares share a point exactly when their x-ranges share a point and their y-ranges share a point. Work out what that means for the gap between two centers on each axis, including the touching case.
- Pairs are counted by index, so k squares with the same center contribute pairs among themselves even though they sit at one location.
- With up to 10^5 squares, checking every pair is too slow. For one square, only centers that are close to it on both axes can overlap it, so look for a way to examine just those.