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

K Closest Points to Origin

Understand how to solve the problem of finding the k closest points to the origin on a 2D plane by calculating Euclidean distances. Learn techniques to efficiently handle unsorted point arrays and return the closest points using practical coding approaches.

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.

JavaScript
usercode > Solution.js
import { MaxHeap, MinHeap } from "./Heap.js"



/* The following definition is for MinHeap.



  You can use the same methods for MaxHeap.

  class MinHeap {



    size();          // return number of elements

    peek();          // return top element without removing

    push(val);       // insert element

    pop();           // remove and return top element

  }

*/



function kClosest(points, k){

    

    // Replace this placeholder return statement with your code

    return -1;

}



export { 

    kClosest

}
K Closest Points to Origin