Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
2.
Problem Statement
3.
Method
4.
Algorithm
5.
Code
6.
Complexity analysis
7.
Frequently Asked Questions
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

Author Malay Gain
0 upvote
gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up

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. 

Also Read, Prefix Sum Array

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.

illustration image

 

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.

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!

Previous article
Reduce the Array to at Most one Element by the Given Operation
Next article
Rearranging String
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass