Count Overlapping Square Pairs
Updated
Problem statement
There are n squares on a plane, and centers[i] = [x, y] is the center of square i. Every square has side length 2 and sides parallel to the axes, so square i covers every point whose x-coordinate is within 1 of centers[i][0] and whose y-coordinate is within 1 of centers[i][1], including its border.
Two squares overlap if they share at least one point. Squares that only touch along an edge or at a corner overlap, and two squares with the same center overlap.
Return the number of pairs (i, j) with i < j whose squares overlap.
Function
countOverlappingPairs(centers: int[][]) → intExamples
Example 1
centers = [[0,0],[1,1],[3,0],[0,5]]return = 2- Squares at
[0,0]and[1,1]: the centers differ by 1 on both axes, so they overlap. - Squares at
[1,1]and[3,0]: the gaps are 2 and 1, so the squares touch along an edge and count as overlapping. [0,0]and[3,0]are 3 apart on x, and[0,5]is at least 4 away on y from every other square, so those pairs do not overlap. The answer is 2.
Example 2
centers = [[2,2],[2,2],[4,4]]return = 3- The two squares at
[2,2]cover the same area, so they overlap. - Each of them meets the square at
[4,4]at exactly one corner, which also counts. That gives 3 pairs.
Example 3
centers = [[-5,7]]return = 0- One square has no other square to pair with, so the answer is 0.
Constraints
1 <= centers.length <= 104centers[i].length == 2-109 <= centers[i][0], centers[i][1] <= 109
More Ramp interview questions
- Count User Mentions in Chat MessagesOA · Seen Nov 2026
- Accept or Decline QueriesOA · Seen Sep 2026
- Recipe Management SystemOA · Seen Mar 2026
- Task Manager with Timed AssignmentsOA · Seen Jan 2026
- Bank Requests with Delayed CashbackOA · Seen Dec 2025
- Convert Snake Case Variables to Camel CaseOA · Seen Apr 2025
- Correct Apartment Bedroom CountsOA · Seen Feb 2025
- Retryable URL MazePHONE SCREEN · Seen Oct 2026
- Detect Recurring Transactions with Tunable TolerancesONSITE INTERVIEW · Seen Jul 2026
- Find a User’s Airport from Flight HistoryPHONE SCREEN · Seen Sep 2025
Similar questions at other companies
- Find Valid SET Card TriplesSnowflake · OA · PHONE SCREENSnowflake interview questions
- Two Tribes from Taller-Person CountsIntuit · OAIntuit interview questions
- Count One-Swap Number PairsCapital One · OACapital One interview questions
- Get Triplet CountIBM · OAIBM interview questions
- Count Reverse-Digit PairsVisa · OAVisa interview questions
- Count 2x2 Submatrices by Black CellsTikTok · OATikTok interview questions
- HTTP Request RedirectionAmazon · OA
- Get Triplet CountPoint72 · OAPoint72 interview questions
- Cheating CodemakerJane Street · OAJane Street interview questions
- Counting Triplets Divisible by DAT&T · OAAT&T interview questions