Quick 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.

Count Overlapping Pairs of 2x2 Squares Given Their Centers

Company: Ramp

Role: Software Engineer

Category: Coding & Algorithms

Difficulty: easy

Interview Round: Online Assessment

You are given the centers of `n` axis-aligned squares, each 2 units wide and 2 units tall. The square centered at `(x, y)` covers every point `(p, q)` with `x - 1 <= p <= x + 1` and `y - 1 <= q <= y + 1`. Count how many pairs of squares overlap. The report does not say how touching squares are treated; this version counts two squares as overlapping when they share at least one point, so squares that touch only along an edge or at a corner count. ### Function Signature ```python def count_overlapping_pairs(centers: list[list[int]]) -> int: ``` ### Rules - `centers[i] = [x, y]` gives the x coordinate first and the y coordinate second. - Squares `i` and `j` overlap when the regions they cover share at least one point, including squares that only touch along an edge or at a corner. - Several squares may have the same center; any two of them overlap. - Count unordered pairs `(i, j)` with `i < j` and return the count as a single integer. ### Constraints - `1 <= n <= 10^5` - `-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`; use a 64-bit integer where integer width matters. ### Examples **Example 1** ```text Input: centers = [[0, 0], [2, 0], [5, 5], [1, 1]] Output: 3 ``` The squares at `(0, 0)` and `(2, 0)` touch along the line `x = 1`. The square at `(1, 1)` overlaps both of them in an area. The square at `(5, 5)` is at least 3 units away in x from every other center, so it overlaps nothing. **Example 2** ```text Input: centers = [[0, 0], [3, 0], [0, 0], [2, 2]] Output: 4 ``` The two squares at `(0, 0)` overlap each other, and each touches the square at `(2, 2)` at the corner `(1, 1)`. The square at `(3, 0)` covers x from 2 to 4 and y from -1 to 1, so it touches the square at `(2, 2)` along the segment `y = 1`, `2 <= x <= 3`, but it does not reach either square at `(0, 0)`, which end at `x = 1`.

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.

You are given the centers of `n` axis-aligned squares. Every square is 2 units wide and 2 units tall: the square centered at `(x, y)` covers every point `(p, q)` with `x - 1 <= p <= x + 1` and `y - 1 <= q <= y + 1`. `centers[i] = [x, y]` gives the x coordinate first and the y coordinate second. Two squares **overlap** when the regions they cover share at least one point. This includes squares that touch only along an edge or only at a corner. Several squares may have the same center; any two of them overlap. Return the number of unordered pairs of indices `(i, j)` with `i < j` whose squares overlap, as a single integer. ### Example 1 ```text Input: centers = [[0, 0], [2, 0], [5, 5], [1, 1]] Output: 3 ``` The squares at `(0, 0)` and `(2, 0)` touch along the line `x = 1`. The square at `(1, 1)` overlaps both of them in an area. The square at `(5, 5)` is at least 3 units away in x from every other center, so it overlaps nothing. ### Example 2 ```text Input: centers = [[0, 0], [3, 0], [0, 0], [2, 2]] Output: 4 ``` The two squares at `(0, 0)` overlap each other, and each touches the square at `(2, 2)` at the corner `(1, 1)`. The square at `(3, 0)` covers x from 2 to 4 and y from -1 to 1, so it touches the square at `(2, 2)` along the segment `y = 1`, `2 <= x <= 3`, but it does not reach either square at `(0, 0)`, which end at `x = 1`. ### 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 it as a 64-bit integer (`long` in Java, `long long` in C++).

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

  1. 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.
  2. Pairs are counted by index, so k squares with the same center contribute pairs among themselves even though they sit at one location.
  3. 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.

Count Overlapping Pairs of 2-by-2 Squares

easyRampSoftware Engineer

You are given the centers of n axis-aligned squares. Every square is 2 units wide and 2 units tall: the square centered at (x, y) covers every point (p, q) with x - 1 <= p <= x + 1 and y - 1 <= q <= y + 1. centers[i] = [x, y] gives the x coordinate first and the y coordinate second.

Two squares overlap when the regions they cover share at least one point. This includes squares that touch only along an edge or only at a corner. Several squares may have the same center; any two of them overlap.

Return the number of unordered pairs of indices (i, j) with i < j whose squares overlap, as a single integer.

Example 1

Input:  centers = [[0, 0], [2, 0], [5, 5], [1, 1]]
Output: 3

The squares at (0, 0) and (2, 0) touch along the line x = 1. The square at (1, 1) overlaps both of them in an area. The square at (5, 5) is at least 3 units away in x from every other center, so it overlaps nothing.

Example 2

Input:  centers = [[0, 0], [3, 0], [0, 0], [2, 2]]
Output: 4

The two squares at (0, 0) overlap each other, and each touches the square at (2, 2) at the corner (1, 1). The square at (3, 0) covers x from 2 to 4 and y from -1 to 1, so it touches the square at (2, 2) along the segment y = 1, 2 <= x <= 3, but it does not reach either square at (0, 0), which end at x = 1.

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 it as a 64-bit integer (long in Java, long long in C++).

Examples

Example 1
Input
([[0, 0], [2, 0], [5, 5], [1, 1]],)
Output
3
Notes
Source example 1: (0,0)-(2,0) touch along an edge, (1,1) overlaps both, (5,5) is isolated.
Example 2
Input
([[0, 0], [3, 0], [0, 0], [2, 2]],)
Output
4
Notes
Source example 2: the duplicate (0,0) pair, both touch (2,2) at a corner, and (3,0) touches (2,2) along an edge.

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++)

Comments (0)

No comments yet. Be the first to comment!

Submit your answer

Approved first answer today earns 30 XP
Bold⌘BItalic⌘IInline code⌘`Bullet listTab to nest (○ ■)Numbered listTab to nest (a. i.)QuoteCode block
Formatting help
Signature
def count_overlapping_pairs(centers: list[list[int]]) -> int:
Sample call
count_overlapping_pairs([[0, 0], [2, 0], [5, 5], [1, 1]])
Language
Case 1
Input
([[0, 0], [2, 0], [5, 5], [1, 1]],)
Expected
3
Case 2
Input
([[0, 0], [3, 0], [0, 0], [2, 2]],)
Expected
4

Browse More Questions

Show the approach

Approach

Overlap test: the closed intervals [a - 1, a + 1] and [b - 1, b + 1] share a point exactly when |a - b| <= 2, and two axis-aligned squares share a point exactly when both their x-ranges and their y-ranges do. So squares i and j overlap if and only if |x_i - x_j| <= 2 and |y_i - y_j| <= 2, which includes edge touches (gap 2 on one axis), corner touches (gap 2 on both) and equal centers.

Algorithm: sort the centers by (x, y). For the center at sorted position i with coordinates (x, y), count the overlapping centers that come later in sorted order. Every such center has x' in {x, x + 1, x + 2}. For x' = x, every later position is already >= (x, y), so the later centers with y' <= y + 2 are exactly positions i + 1 up to lower_bound((x, y + 3)) - 1. For x' = x + 1 or x + 2, the matching centers form the contiguous block from lower_bound((x', y - 2)) up to lower_bound((x', y + 3)) - 1. Here lower_bound((tx, ty)) is a binary search for the first sorted center that is not smaller than (tx, ty) in (x, y) order. The answer is the sum of these counts over all i.

Correctness: in any overlapping pair, one member comes first in sorted order. Seen from that earlier position, the later member lies in exactly one of the three blocks, so it is counted there. Seen from the later position, the counting only looks at even later positions or larger x, so the pair is never counted again. Every unordered pair is therefore counted exactly once. Duplicate centers sit next to each other and fall in the same-x block, giving k * (k - 1) / 2 pairs for k copies.

Edge cases: a single center gives 0. The code compares coordinates instead of subtracting them, and the extreme probes y + 3 = 10^9 + 3 and x + 2 = 10^9 + 2 still fit a 32-bit int. The total can reach about 5 * 10^9, so it is accumulated in a 64-bit integer (Python int, a JavaScript number below 2^53, Java long, C++ long long).

Time complexity:
O(n log n)
Space complexity:
O(n)