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

K Closest Points to Origin

Explore how to solve the problem of finding the k closest points to the origin on an X-Y plane. Understand Euclidean distance measurement and learn to apply heaps for efficient top k element selection. This lesson equips you to implement and optimize solutions handling spatial data in 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