Home/

...

/

K Closest Points to Origin

K Closest Points to Origin

Try to solve the K Closest Points to Origin problem.

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

Press + to interact
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]]

Question 1 of 30 attempted

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.

Press + to interact
Python
usercode > Solution.py
def k_closest(points, k):

    

    # Replace this placeholder return statement with your code

    return []
K Closest Points to Origin

Access this course and 1200+ top-rated courses and projects.