Top K Frequent Closest Points
Updated
Problem statement
You are given an array of two-dimensional integer points. Equal coordinate pairs represent repeated observations of the same distinct point.
Return the k distinct points with the highest frequencies, ordered by:
- higher frequency first;
- smaller squared Euclidean distance
x*x + y*yfrom the origin; - smaller
xcoordinate; - smaller
ycoordinate.
Return each selected point once.
Function
topKFrequentClosest(points: int[][], k: int) → int[][]Examples
Example 1
points = [[1,1],[1,1],[2,0],[2,0],[2,0],[0,3]]k = 2return = [[2,0],[1,1]][2,0] occurs three times and [1,1] occurs twice, so frequency fixes their order.
Example 2
points = [[3,0],[0,2],[-2,0],[3,0],[0,2],[-2,0]]k = 3return = [[-2,0],[0,2],[3,0]]All three points occur twice. The two distance-four points tie on distance, so smaller x puts [-2,0] first; [3,0] is farther away.
Constraints
1 <= points.length <= 200000- Every row has exactly two integers
xandywith-100000 <= x, y <= 100000. 1 <= k <=the number of distinct coordinate pairs.- Use signed 64-bit arithmetic for squared distances.
More Google Phone Screen questions
- Best Stock Trade with Buy and Sell DaysPHONE SCREEN · Seen Nov 2026
- Word Chain Jumps in a GridPHONE SCREEN · Seen Nov 2026
- Dice-Walk Winning ProbabilityPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Lowest Common Ancestor in an N-ary TreePHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Apartment Housemate PreferencesPHONE SCREEN · Seen Nov 2026
- Price at Query TimestampsPHONE SCREEN · Seen Nov 2026
- Course Schedule Cycle DetectionPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
- Logger Rate Limiter with Every-Arrival HistoryPHONE SCREEN · Seen Nov 2026
- Minimum Total Layover WaitPHONE SCREEN · Seen Nov 2026
- Reach a Destination Through Scheduled FlightsPHONE SCREEN · ONSITE INTERVIEW · Seen Nov 2026
Similar questions at other companies
- Top K Frequent ElementsAmazon · OA · PHONE SCREEN
- The k Points Nearest the OriginAdobe · PHONE SCREENAdobe interview questions
- Top K Frequent ElementsApple · PHONE SCREENApple interview questions
- Top K Frequent ElementsC3.ai · PHONE SCREENC3.ai interview questions
- K Closest Points to the OriginSambaNova Systems · PHONE SCREENSambaNova Systems interview questions
- Smallest Range Covering Elements from K ListsSnap Inc. · PHONE SCREENSnap Inc. interview questions
- Top K Frequent ElementsCapgemini · ONSITE INTERVIEWCapgemini interview questions
- Mutual-Friend RecommendationsMeta · ONSITE INTERVIEWMeta interview questions
- Top K Frequent Elements with Larger-Value Tie BreakOracle · ONSITE INTERVIEWOracle interview questions
- Top K Frequent ElementsInfosys · ONSITE INTERVIEWInfosys interview questions