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

K Closest Points to Origin

Explore how to find the k closest points to the origin on a 2D plane by calculating Euclidean distances. Learn to implement efficient solutions that handle input constraints and return unique results in any order, enhancing your problem-solving skills 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.

C++
usercode > Solution.cpp
vector<vector<int>> KClosest(vector<vector<int>>& points, int k) {
    
    // Replace this placeholder return statement with your code
    return {};
}
K Closest Points to Origin