FastPrepTop K Frequent Closest Points
Problem · Array

Top K Frequent Closest Points

Learn this problem
● MediumGoogle logoGoogleFULLTIMEPHONE SCREEN
See Google hiring insights

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:

  1. higher frequency first;
  2. smaller squared Euclidean distance x*x + y*y from the origin;
  3. smaller x coordinate;
  4. smaller y coordinate.

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 x and y with -100000 <= x, y <= 100000.
  • 1 <= k <= the number of distinct coordinate pairs.
  • Use signed 64-bit arithmetic for squared distances.

More Google problems

drafts saved locally
public int[][] topKFrequentClosest(int[][] points, int k) {
    // Write your code here.
}
points[[1,1],[1,1],[2,0],[2,0],[2,0],[0,3]]
k2
expected[[2,0],[1,1]]
checking account