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).

You may return the answer in any order. The answer is guaranteed to be unique (except for the order that it is in).

&nbsp;
Example 1:

Input: points = [[1,3],[-2,2]], k = 1
Output: [[-2,2]]
Explanation:
The distance between (1, 3) and the origin is sqrt(10).
The distance between (-2, 2) and the origin is sqrt(8).
Since sqrt(8) &lt; sqrt(10), (-2, 2) is closer to the origin.
We only want the closest k = 1 points from the origin, so the answer is just [[-2,2]].


Example 2:

Input: points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]
Explanation: The answer [[-2,4],[3,3]] would also be accepted.


&nbsp;
Constraints:


	1 &lt;= k &lt;= points.length &lt;= 104
	-104 &lt; xi, yi &lt; 104


def cal(ele):
    return ele[0]**2 +ele[1]**2

def partition(arr,start,end):
    # We must take a pivot element randomly to make Quick select work faster
    rdIdx = randint(start,end)
    arr[rdIdx],arr[end] = arr[end],arr[rdIdx]
    pivot = arr[end]
    i = start-1
    pivot_dis = cal(pivot)
    for j in range(start,end):
        if cal(arr[j]) <= pivot_dis:
            i+=1
            arr[j],arr[i] = arr[i],arr[j]

    arr[i+1],arr[end] = arr[end],arr[i+1]
    return i+1
def qSelect(arr,kth,start,end):
    if start < end:
        pv= partition(arr,start,end)
        # _______________________
        # | Left |ele| Right|
        # ------------------------
        # pv
        # after partition function call, pv is the index that sacrify:
        # all elements in Left will smaller than ele
        # all elements in Right side will greater than ele
        if pv == kth:#
            return
        if kth < pv:
            return qSelect(arr,kth,start,pv-1)
        else:
            return qSelect(arr,kth,pv+1,end)
# Space O (logn) because of using recursion
# Time: Average case: O(N)
# Worst case: O(N**2)
class Solution:
    def kClosest(self, points, k):
        # print(points)
        qSelect(points,k-1,0,len(points)-1)# kth smallest number will be at (k-1) index in sorted array
        return points[:k]
class Solution {
    static class Distance {
        int i;
        int j;
        double dist;

        public Distance(int i, int j, double dist) {
            this.i = i;
            this.j = j;
            this.dist = dist;
        }
    }

    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<Distance> pq = new PriorityQueue<>((x,y) -> Double.compare(x.dist, y.dist));
        for(int[] point : points) {
            double dist = calcDistance(point[0], point[1]);
            pq.offer(new Distance(point[0], point[1], dist));
        }
        int cnt = 0;
        ArrayList<int[]> l = new ArrayList<>();
        while(cnt < k) {
            Distance d = pq.poll();
            l.add(new int[]{d.i, d.j});
            cnt++;
        }
        int[][] res = l.toArray(new int[l.size()][]);
        return res;
    }

    private double calcDistance(int i, int j) {
       double dist = Math.sqrt(Math.pow(i,2) + Math.pow(j,2));
       return dist;
    }
}
class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k)
    {
        //max heap
        priority_queue<pair<int,pair<int,int>>> pq;//first integer is distance(no need for sq root as comparison is same and next part of pair is coordinate
        int n= points.size();
        for(int i=0;i<n;i++)
        {
            int dist=(points[i][0]*points[i][0]+points[i][1]*points[i][1]);
            pq.push({dist, {points[i][0],points[i][1]}});
            if(pq.size()>k)
                pq.pop();
        }
        vector<vector<int>> ans;
        while(!pq.empty())
        {
            vector<int> temp={(pq.top().second.first),pq.top().second.second};
            ans.push_back(temp);
            pq.pop();
        }
        return ans;
    }
};
/**
 * @param {number[][]} points
 * @param {number} k
 * @return {number[][]}
 */
var kClosest = function(points, k) {
    let res = [];
    let hashMap = new Map();
    for(let i = 0; i < points.length; i++) {
		//store the distance and the index of the points in a map
        const dis = calcDis(points[i]);
        hashMap.set(i, dis);
    }
	//sort the map by its distance to the origin
    const hashMapNew = new Map([...hashMap].sort((a,b) => a[1] - b[1]));
	//use the index sorted by distance to get the result
    let i = 0;
    for(const x of hashMapNew.keys()) {
		//do it k times
        if(i === k) break;
        res.push(points[x]);
        i++;
    }
    return res;
};
var calcDis = (b) => {
    return Math.sqrt( Math.pow(b[0], 2) + Math.pow(b[1], 2) );
}
K Closest Points to Origin