K Closest Points to a given Target point
Given a list of points on the 2-D plane arr[][], a given point target, and an integer K. The task is to find K closest points to the target from the given list of points.
Note: The distance between two points on a plane is the Euclidean distance.
Examples:
Input: points = [[3, 3], [5, -1], [-2, 4]], target = [0, 0], K = 2
Output: [[3, 3], [-2, 4]]
Explanation: Square of Distance of target(=origin) from this point is
(3, 3) = 18
(5, -1) = 26
(-2, 4) = 20
So the closest two points are [3, 3], [-2, 4].Input: points = [[1, 3], [-2, 2]], target = [0, 1], K = 1
Output: [[1, 3]]
Approach: The solution is based on Greedy approach. The idea is to calculate the Euclidean distance from the target for every given point and store them in an array. Then sort the array according to the Euclidean distance found and print the first k closest points from the list.
Below is the implementation of above approach.
C++
// C++ program to implement of above approach #include <bits/stdc++.h> using namespace std; // Calculate the Euclidean distance // between two points float distance( int x1, int y1, int x2, int y2) { return sqrt ( pow ((x1 - x2), 2) + pow ((y1 - y2), 2)); } // Function to calculate K closest points vector<vector< int > > kClosest( vector<vector< int > >& points, vector< int > target, int K) { vector<vector< int > > pts; int n = points.size(); vector<pair< float , int > > d; for ( int i = 0; i < n; i++) { d.push_back( make_pair(distance(points[i][0], points[i][1], target[0], target[1]), i)); } sort(d.begin(), d.end()); for ( int i = 0; i < K; i++) { vector< int > pt; pt.push_back(points[d[i].second][0]); pt.push_back(points[d[i].second][1]); pts.push_back(pt); } return pts; } // Driver code int main() { vector<vector< int > > points = { { 1, 3 }, { -2, 2 } }; vector< int > target = { 0, 1 }; int K = 1; for ( auto pt : kClosest(points, target, K)) { cout << pt[0] << " " << pt[1] << endl; } return 0; } |
Java
// Java program to implement of above approach import java.util.*; class GFG{ static class pair { float first; float second; public pair( float f, float second) { this .first = f; this .second = second; } } // Calculate the Euclidean distance // between two points static float distance( int x1, int y1, int x2, int y2) { return ( float ) Math.sqrt(Math.pow((x1 - x2), 2 ) + Math.pow((y1 - y2), 2 )); } // Function to calculate K closest points static Vector<Vector<Integer> > kClosest( int [][] points, int [] target, int K) { Vector<Vector<Integer>> pts = new Vector<Vector<Integer>>(); int n = points.length; Vector<pair> d = new Vector<pair>(); for ( int i = 0 ; i < n; i++) { d.add( new pair(distance(points[i][ 0 ], points[i][ 1 ], target[ 0 ], target[ 1 ]), i)); } Collections.sort(d, (a, b) -> ( int )(a.first - b.first)); for ( int i = 0 ; i < K; i++) { Vector<Integer> pt = new Vector<Integer>(); pt.add(points[( int ) d.get(i).second][ 0 ]); pt.add(points[( int ) d.get(i).second][ 1 ]); pts.add(pt); } return pts; } // Driver code public static void main(String[] args) { int [][] points = { { 1 , 3 }, { - 2 , 2 } }; int [] target = { 0 , 1 }; int K = 1 ; for (Vector<Integer> pt : kClosest(points, target, K)) { System.out.print(pt.get( 0 )+ " " + pt.get( 1 ) + "\n" ); } } } // This code is contributed by 29AjayKumar |
Python3
# Python code for the above approach # Calculate the Euclidean distance # between two points def distance(x1, y1, x2, y2): return ((x1 - x2) * * 2 + (y1 - y2) * * 2 ) * * ( 1 / 2 ) # Function to calculate K closest points def kClosest(points, target, K): pts = [] n = len (points) d = [] for i in range (n): d.append({ "first" : distance(points[i][ 0 ], points[i][ 1 ], target[ 0 ], target[ 1 ]), "second" : i }) d = sorted (d, key = lambda l:l[ "first" ]) for i in range (K): pt = [] pt.append(points[d[i][ "second" ]][ 0 ]) pt.append(points[d[i][ "second" ]][ 1 ]) pts.append(pt) return pts # Driver code points = [[ 1 , 3 ], [ - 2 , 2 ]] target = [ 0 , 1 ] K = 1 for pt in kClosest(points, target, K): print (f "{pt[0]} {pt[1]}" ) # This code is contributed by gfgking. |
C#
// C# program to implement of above approach using System; using System.Collections.Generic; public class GFG { public class pair { public float first; public float second; public pair( float f, float second) { this .first = f; this .second = second; } } // Calculate the Euclidean distance // between two points static float distance( int x1, int y1, int x2, int y2) { return ( float ) Math.Sqrt(Math.Pow((x1 - x2), 2) + Math.Pow((y1 - y2), 2)); } // Function to calculate K closest points static List<List< int >> kClosest( int [,] points, int [] target, int K) { List<List< int >> pts = new List<List< int >>(); int n = points.GetLength(0); List<pair> d = new List<pair>(); for ( int i = 0; i < n; i++) { d.Add( new pair(distance(points[i,0], points[i,1], target[0], target[1]), i)); } for ( int i = 0; i < K; i++) { List< int > pt = new List< int >(); pt.Add(points[( int ) d[i].second,0]); pt.Add(points[( int ) d[i].second,1]); pts.Add(pt); } return pts; } // Driver code public static void Main(String[] args) { int [,] points = { { 1, 3 }, { -2, 2 } }; int [] target = { 0, 1 }; int K = 1; foreach (List< int > pt in kClosest(points, target, K)) { Console.Write(pt[0] + " " + pt[1] + "\n" ); } } } // This code is contributed by Rajput-Ji |
Javascript
<script> // JavaScript code for the above approach // Calculate the Euclidean distance // between two points function distance(x1, y1, x2, y2) { return Math.sqrt(Math.pow((x1 - x2), 2) + Math.pow((y1 - y2), 2)); } // Function to calculate K closest points function kClosest(points, target, K) { let pts = []; let n = points.length; let d = []; for (let i = 0; i < n; i++) { d.push({ first: distance(points[i][0], points[i][1], target[0], target[1]), second: i }); } d.sort( function (a, b) { return a.first - b.first }) for (let i = 0; i < K; i++) { let pt = []; pt.push(points[d[i].second][0]); pt.push(points[d[i].second][1]); pts.push(pt); } return pts; } // Driver code let points = [[1, 3], [-2, 2]]; let target = [0, 1]; let K = 1; for (let pt of kClosest(points, target, K)) { document.write(pt[0] + " " + pt[1] + '<br>' ); } // This code is contributed by Potta Lokesh </script> |
1 3
Time Complexity: O(N * logN)
Auxiliary Space: O(N)
Contact Us