Search⌘ K
AI Features
Home
Courses
Grokking the Coding Interview Patterns

K Closest Points to Origin

Explore how to find the k closest points to the origin in a 2D plane by applying heap data structures. Understand Euclidean distance calculation and implement top k selection techniques. This lesson helps you solve proximity problems commonly asked in coding interviews, building a foundation for advanced top k element challenges.

We'll cover the following...

Statement

You are given an array of points where each element points[i] =[xi,yi]= [x_i, y_i] represents a point on the X-Y plane, along with an integer k. Your task is to find and return the k points that are closest to the origin [0,0][0, 0].

The distance between two points on the X-Y plane is measured using Euclidean distance, which is calculated as:

Note: You can return the result in any order. The answer is guaranteed to be unique, except for the order in which points appear.

Constraints:

  • 1≤1 \leq k ≤\leq points.length ≤103\leq 10^3

  • −104≤xi,yi≤104-10^4 \leq x_i, y_i \leq 10^4

Examples

canvasAnimation-image
1 / 4

Understand the problem

Let’s take a moment to make sure you’ve correctly understood the problem. The quiz below helps you check if you’re solving the correct problem:

K Closest Points to Origin

1.

(Select all that apply.) What is the output if the following data is given as an input?

points =[[1,3],[−2,4],[2,−1],[−2,2],[5,−3],[3,−2]]= [[1, 3], [-2, 4], [2, -1], [-2, 2], [5, -3], [3, -2]]

k =3= 3

A.

[[1,3],[−2,2],[5,−3]][[1, 3], [-2, 2], [5, -3]]

B.

[[1,3],[2,−1],[−2,2]][[1, 3], [2, -1], [-2, 2]]

C.

[[2,−1],[−2,4],[1,3]][[2, -1], [-2, 4], [1, 3]]

D.

[[1,3],[−2,2],[3,−2]][[1, 3], [-2, 2], [3, -2]]

1 / 3

Figure it out!

We have a game for you to play. Rearrange the logical building blocks to develop a clearer understanding of how to solve this problem.

Sequence - Vertical
Drag and drop the cards to rearrange them in the correct sequence.
1
2
3
4
5

Try it yourself

Implement your solution in the following coding playground.

Java
usercode > Solution.java
public class Solution{
    public int[][] kClosest(int[][] points, int k) {
        
        // Replace this placeholder return statement with your code
        return new int[0][];
    }
}
K Closest Points to Origin