K Closest Points to Origin

Try to solve the K Closest Points to Origin problem.

We'll cover the following

Statement#

Given a list of points on a plane, where the plane is a 2-D array with (x, y) coordinates, find the $k$ closest points to the origin $(0, 0)$ .

Note: Here, the distance between two points on a plane is the Euclidean distance: $\sqrt{x^2 + y^2}$

Constraints:

1 of 4

2 of 4

3 of 4

4 of 4

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

What is the output if the following list of points and value of k is given as input?

Select all that apply.

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

k = 3

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

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

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

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

Question 1 of 40 attempted

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

Drag and drop the cards to rearrange them in the correct sequence.

Push the first k points to the heap.

Calculate the distance between the origin and each point.

Compare the distance of the point with the distance of the top of the heap.

Push and pop the point from the heap.

Return the points from the heap.

Implement your solution in main.py and point.py in the following coding playground.

A Point class has two data members, x and y coordinates. You may add members or methods to it to support your solution.

Note: The order of the points returned is not significant.

Python

main.py

point.py

from point import Point
import heapq
def k_closest(points, k):
  
    # Replace this placeholder return statement with your code
    return []

f

Enter to Rename, Shift+Enter to Preview

Input #1

Input #2

K Closest Points to Origin

Top K Elements: Introduction

Solution: K Closest Points to Origin