1.
Introduction
2.
Problem Statement
3.
Method
4.
Algorithm
5.
Code
6.
Complexity analysis
7.
7.1.
What is Euclidean distance?
7.2.
What is a hash map?
7.3.
What kind of sorting is used in the C++ STL sort() function?
8.
Conclusion
Last Updated: Mar 27, 2024

K Closest Points To Origin

Malay Gain
0 upvote
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems

Introduction

K Closest Points To Origin is a simple problem that can be solved using the brute force approach. Here we will discuss the approach and complexity of the algorithm.

Problem Statement

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., âˆš(x1 - x2)^2 + (y1 - y2)^2).

Input:

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

k = 2

Output: [[3,3],[-2,4]]    (these are the 2 closest points among 3 points)

See the below diagram for a better understanding.

Note: Please try to solve the problem first and then see the below solution approach.

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Method

Here we will take nothing but a brute-force approach to solve this problem. First, we will iterate through all the points and find the corresponding distances from the origin for each point. Then we will find k shortest distances and corresponding points.

For finding the k shortest distances, we need to store the distance and index of the corresponding point. Then we sort the distances and print the first k points corresponding to distances.

Algorithm

• Iterate over the array of points.
• Find the Euclidean distance of each point from the origin.
• Use a hashmap to store the distance and corresponding pointâ€™s index
• Sort the hashmap according to the distances
• Print the k points using the first k indices in the hash map. These are the closest points to the origin.

Code

``````// c++ code to find  k-closest-points-to-origin

#include<bits/stdc++.h>
using namespace std;

vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {

vector<pair<int,int>> m;
vector<vector<int>> closest;
for(int i=0;i<points.size();i++)
{
int dist=(pow(points[i][0],2)+pow(points[i][1],2));

m.push_back({dist,i});
//using hash map to store the distance and corresponding //point's index
}

sort(m.begin(),m.end());// Sorting the hash map according to the // distances

int i=1;

//storing k points using the first k indices in the hash map
for(auto id:m)
{
if(i>k)
{
return closest;
}

closest.push_back(points[id.second]);
i++;
}

return closest;
}

// driver code

int main()
{
vector<vector<int>> points;

points.push_back({3,3});
points.push_back({5,-1});
points.push_back({-2,4});

int k=2;

vector<vector<int>> closest=kClosest(points,k);

for(auto point:closest)
{
cout<<"("<<point[0]<<","<<point[1]<<")"<<endl;
}
}``````

Output

``````(3,3)
(-2,4)``````

Complexity analysis

Here the time complexity of the algorithm for finding k closest points is O(nlog n) where n is the number of points.

Space complexity is O(n) as we are using extra space for a hash map.

You can also explore about GCD Euclidean Algorithm here.

What is Euclidean distance?

Euclidean distance between two points (x1,y1) and (x2,y2) is

âˆš(x1 - x2)^2 + (y1 - y2)^2)

What is a hash map?

It is a special kind of data structure that is used to store a unique key and associated value(key-value pair).

What kind of sorting is used in the C++ STL sort() function?

It uses a hybrid sorting algorithm of insertion sort, heap sort, and quicksort.

Conclusion

Apart from this, you can practice a wide range of coding questions commonly asked in interviews in Coding Ninjas Studio. Along with coding questions, we can also find the interview experience of scholars working in renowned product-based companies here.

Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Happy learning!

Guided path
Free
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems