Count Squares of Any Orientation
Updated
Problem statement
You are given distinct points in a two-dimensional plane. Count the squares whose four corners are input points.
Squares may be tilted; their sides do not need to follow the coordinate axes. Count each set of four corners once. Do not count shapes with zero area.
Function
solution(points: int[][]) → intExamples
Example 1
points = [[0,0],[1,0],[0,1],[1,1]]return = 1The four points form one unit square.
Example 2
points = [[0,1],[1,0],[2,1],[1,2]]return = 1These points form one rotated square, which must be counted.
Example 3
points = [[0,0],[2,0],[0,1],[2,1]]return = 0The four points form a rectangle with unequal side lengths.
Example 4
points = [[0,0],[0,1],[0,2],[1,0],[1,1],[1,2],[2,0],[2,1],[2,2]]return = 6There are four unit squares, one larger axis-aligned square and one rotated square.
Constraints
0 <= points.length <= 2000.- Each row of
pointscontains two integers[x, y], with-10000 <= x, y <= 10000. - All input points are distinct.
More Marshall Wace interview questions
- Maximum Sum with at Most Three Two-Element TilesPHONE SCREEN · Seen Sep 2025
- Minimum Full Glasses for an Exact Water VolumePHONE SCREEN · Seen Sep 2025
- Smallest Absolute Difference Between Two Array ElementsPHONE SCREEN · Seen Sep 2025
- Maximum Frog Separation with One Upward Jump (Practice Reconstruction)PHONE SCREEN · Seen Jul 2023
- Minimum Deletions Before Rearranging into a PalindromePHONE SCREEN · Seen Jul 2023
- Smallest Larger Integer with Twice the Digit SumPHONE SCREEN · Seen Jul 2023
- Count Letters with Ordered Lowercase and Uppercase OccurrencesOA · Seen Oct 2025
- Maximum Trailing Zeros on a Path with at Most One TurnOA · Seen Oct 2025
- Shortest Subarray Covering an Integer RangeOA · Seen Oct 2025
- Maximum Events in a 60-Second WindowOA · Seen Aug 2025
Similar questions at other companies
- Find All Points Within a RadiusGoogle · PHONE SCREENGoogle interview questions
- Group Sparse Points by Distance ThresholdNuro · PHONE SCREENNuro interview questions
- Max Points on a LineUber · PHONE SCREENUber interview questions
- Merge Collinear Point SegmentsApplied Intuition · PHONE SCREENApplied Intuition interview questions
- Count Overlapping Square PairsRamp · OARamp interview questions
- HTTP Request RedirectionAmazon · OA
- Members Lacking Provider Network AccessOscar Health · ONSITE INTERVIEW
- Max Points on a LineLinkedIn · ONSITE INTERVIEWLinkedIn interview questions
- Max Points on a LineMicrosoft · ONSITE INTERVIEWMicrosoft interview questions
- Merchant Payout Scheduler, Part 2: Per-Merchant SchedulesStripe · PHONE SCREENStripe interview questions