K Closest Points to Origin Leetcode Solution

Difficulty Level Medium
Frequently asked in Amazon Asana Facebook Google LinkedIn Microsoft
Array Divide and Conquer Geometry Heap Math Sorting Sumologic tiktokViews 3555

Problem Statement

The K Closest Points to Origin LeetCode Solution – “K Closest Points to Origin” states that given an array of points, x coordinates and y coordinates represent the coordinates on XY Plane. We need to find k closest points to the origin.

Note that the distance between two points is equal to the Euclidean Distance between them.

Example:

K Closest Points to Origin Leetcode Solution

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

Explanation:

  • (1,3) has a distance of sqrt(10) units while (-2,2) has a distance of sqrt(8) units.
  • We need to return only 1 point which has the minimum distance, Hence (-2,2) is the required answer.
Input:  points = [[3,3],[5,-1],[-2,4]], k = 2
Output: [[3,3],[-2,4]]

Explanation:

  • Distance of (3,3) from the origin is sqrt(18) units, Distance of (5,-1) from the origin is sqrt(26) units and Distance of (-2,4) from the origin is sqrt(20) units.
  • Hence our answer is (3,3) and (-2,4).

Approach

Idea:

  1. The main idea to solve this problem is to use Priority Queue.
  2. For all the coordinates, calculate the euclidean distance of the current point from the origin.
  3. Push the distance along with coordinates in the priority queue (max heap).
  4. If the size of the priority queue exceeds the value of k, we need to pop out the coordinate with maximum euclidean distance from the origin and that coordinate will be present at the top of the priority queue.
  5. Finally, we are left with k closest points in the priority queue.

Code

K Closest Points to Origin Leetcode C++ Solution:

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        priority_queue<vector<int>> q;
        for(auto& point:points){
            int x = point[0],y = point[1];
            int d = x*x + y*y;
            q.push({d,x,y});
            if(q.size()>k){
                q.pop();
            }
        }
        vector<vector<int>> ans;
        while(!q.empty()){
            ans.push_back({q.top()[1],q.top()[2]});
            q.pop();
        }
        return ans;
    }
};

K Closest Points to Origin Leetcode Java Solution:

class Solution {
    public int[][] kClosest(int[][] points, int k) {
        PriorityQueue<int[]> pq = new PriorityQueue<int[]>((point1, point2) -> point2[0] * point2[0] + point2[1] * point2[1] - point1[0] * point1[0] - point1[1] * point1[1]);
        for (int[] point : points) {
            pq.offer(point);
            if (pq.size() > k) {
                pq.poll();
            }
        }
        int[][] ans = new int[k][2];
        while (k > 0) {
            ans[--k] = pq.poll();
        }
        return ans; 
    }
}

Complexity Analysis for K Closest Points to Origin Leetcode Solution

Time Complexity

The time complexity of the above code is O(NlogK) since we traverse the entire input array once, and each point will be pushed into the max heap (size k) once where N = size of the input array and K = size of the max heap.

Space Complexity

The space complexity of the above code is O(K) since we’re maintaining a max heap of maximum size k.

Translate »