K Closest Points to a given Target point

0 0 4 minutes read

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>

Output

1 3

Time Complexity: O(N * logN)
Auxiliary Space: O(N)

Recommended

Solve DSA problems on GfG Practice.

Solve Problems

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 zambiatek!