K Closest Points To Origin

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;
}
}

You can also try this code with Online C++ Compiler

Run Code

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.

Frequently Asked Questions

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

This article covered how to find K Closest Points To Origin.

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!