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

K Closest Points to Origin

Explore how to identify the k closest points to the origin from a list of 2D points by applying the top k elements pattern. Understand Euclidean distance calculation and practice implementing efficient solutions using heaps to optimize selection for coding interviews.

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.

Python
usercode > Solution.py
def k_closest(points, k):

    

    # Replace this placeholder return statement with your code

    return []
K Closest Points to Origin