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 pointsfloat distance(int x1, int y1, int x2, int y2){ return sqrt(pow((x1 - x2), 2) + pow((y1 - y2), 2));}// Function to calculate K closest pointsvector<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 codeint 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 approachimport 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 pointsstatic 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 pointsstatic 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 codepublic 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 pointsdef distance(x1, y1, x2, y2): return ((x1 - x2) ** 2 + (y1 - y2) ** 2) ** ( 1 / 2)# Function to calculate K closest pointsdef 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 codepoints = [[1, 3], [-2, 2]]target = [0, 1]K = 1for 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 approachusing 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> |
Output
1 3
Time Complexity: O(N * logN)
Auxiliary Space: O(N)
Feeling lost in the world of random DSA topics, wasting time without progress? It’s time for a change! Join our DSA course, where we’ll guide you on an exciting journey to master DSA efficiently and on schedule.
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
Ready to dive in? Explore our Free Demo Content and join our DSA course, trusted by over 100,000 neveropen!
