Solution For K Closest Points To Origin

Problem Statement:

We have a list of points in the plane. Find the K closest points to the origin (0, 0).

Input: points = [[1,3],[-2,2]], K = 1
Output: [[-2,2]]

Input: points = [[3,3],[5,-1],[-2,4]], K = 2
Output: [[3,3],[-2,4]]

Approach:

1. Calculate the distance of each point in the given list from the origin using the distance formula (sqrt(x^2+y^2)).
2. Create a max heap and push the first K points into it.
3. For the remaining points, calculate the distance from the origin and compare it with the maximum distance in the heap.
4. If the new point has a smaller distance, remove the maximum distance from the heap and add the new point.
5. At the end, the heap will contain the K closest points to the origin.

Solution:

We can implement a min heap and store the distances in it instead of the points itself. This will optimize the space used.

Time Complexity: O(nlogk)
Space Complexity: O(k)

Here is the python code for the solution:

import heapq
class Solution:
def kClosest(self, points: List[List[int]], K: int) -> List[List[int]]:

    heap = []
    for point in points:
        distance = -1*(point[0]**2 + point[1]**2) # calculate negative distance to implement max heap as a min heap
        if len(heap) < K:
            heapq.heappush(heap, (distance, point))
        else:
            if heap[0][0] < distance:
                heapq.heappop(heap)
                heapq.heappush(heap, (distance, point))

    result = []
    for element in heap:
        result.append(element[1])

    return result

This will give us the K closest points to the origin.

Step by Step Implementation For K Closest Points To Origin

class Solution {
    public int[][] kClosest(int[][] points, int K) {
        // create a max heap
        PriorityQueue pq = new PriorityQueue<>((p1, p2) -> p2[0] * p2[0] + p2[1] * p2[1] - p1[0] * p1[0] - p1[1] * p1[1]);
        
        // push all points into the max heap
        for (int[] p : points) {
            pq.add(p);
        }
        
        // pop from the heap until we have K points
        int[][] res = new int[K][2];
        for (int i = 0; i < K; i++) {
            res[i] = pq.poll();
        }
        return res;
    }
}

def kClosest(points, K): 
    
    # dist_sq stores the squared Euclidean distance 
    # from the origin, for each point in points 
    dist_sq = [(x*x + y*y) for (x, y) in points] 
    
    # index stores the original index of each point 
    index = [i for i in range(len(points))] 
    
    # Sort the points according to their squared 
    # Euclidean distance from the origin 
    dist_sq, index = zip(*sorted(zip(dist_sq, index))) 
    
    # Return the first K points from the sorted list 
    return [points[i] for i in index[:K]]

var kClosest = function(points, K) {
    // sort the points by their distance from the origin
    points.sort((a, b) => (a[0]**2 + a[1]**2) - (b[0]**2 + b[1]**2));
    
    // return the first K points
    return points.slice(0, K);
};

We can use a priority queue to store the points sorted by their distance from the origin. Then, we can pop the first k points off of the queue to get the k closest points.

#include  #include  #include  using namespace std; // A comparator function to sort points by their distance from the origin struct Compare { bool operator()(const vector& p1, const vector& p2) { // Calculate the distance from the origin for each point double d1 = sqrt(pow(p1[0], 2) + pow(p1[1], 2)); double d2 = sqrt(pow(p2[0], 2) + pow(p2[1], 2)); // Return true if point 1 is closer to the origin than point 2 return d1 < d2; } }; vector> kClosest(vector>& points, int k) { // Create a priority queue to store the points sorted by distance from the origin priority_queue, vector>, Compare> pq; // Push all points into the queue for (auto& point : points) { pq.push(point); } // Pop the first k points off of the queue to get the k closest points vector> closestPoints; for (int i = 0; i < k; i++) { closestPoints.push_back(pq.top()); pq.pop(); } return closestPoints; }

using System; using System.Collections.Generic; using System.Linq; namespace ConsoleApplication1 { class Program { static void Main(string[] args) { int[][] points = new int[][] { new int[] { 1, 3 }, new int[] { -2, 2 } }; int K = 1; var result = KClosest(points, K); foreach (var item in result) { Console.WriteLine("{0},{1}", item[0], item[1]); } Console.ReadLine(); } public static int[][] KClosest(int[][] points, int K) { //To store the result int[][] result = new int[K][]; //To store the distance of each point from origin List distance = new List(); //Calculating the distance of each point from origin for (int i = 0; i < points.Length; i++) { int d = points[i][0] * points[i][0] + points[i][1] * points[i][1]; distance.Add(d); } //Sorting the list in ascending order distance.Sort(); //Adding the K closest points to result for (int i = 0; i < K; i++) { for (int j = 0; j < points.Length; j++) { if ((points[j][0] * points[j][0] + points[j][1] * points[j][1]) == distance[i]) { result[i] = points[j]; } } } return result; } } }