Find the K closest points to origin using Priority Queue

Introduction

This blog will discuss the solution to this problem to find the k closest points to origin using priority queue. So before we deep dive into the answer, we should look at some examples to understand the problem better.

Some Examples

Input:

 [(1, 0), (2, 2), (1,3), (0,-4)]   K=2

Output: 

[(1, 0), (2, 2)]

Explanation:

  • Square of Distance of (1, 0) from the origin is 1
  • Square of Distance of (1, 3) form the origin is 10
  • Square of Distance of (2, 2) from the origin is 8
  • Square of Distance of (0, -4) from the origin is 16 

Therefore for K = 2, the closest points are (1, 0) & (2, 2)

Input:

[(2, 1), (-3, -2), (3, 0), (0, -2), (3, -1)]   K = 3

Output:

[(0, -2), (2, 1), (3, 0)] 

Explanation:

  • Square of Distance of (2, 1) from the origin is 5
  • Square of Distance of (-3, -2) form the origin is 13
  • Square of Distance of (3, 0) from the origin is 9
  • Square of Distance of (0, -2) from the origin is 4
  • Square of Distance of (3, -1) from the origin is 10

Therefore for K = 3, the closest points are (0, -2), (2, 1) & (3, 0)

*Square of Distance = x*x + y*y

Priority Queue Approach

To solve this problem, find the K closest points to origin using priority queue; we will first create a min-heap of pairs in which we will store the distance of the point from the origin and the point itself, and after that, we will traverse the min-heap till K. Simultaneously we will store all the points in our final array. After that, we will return the array.

Algorithm

  1. To solve this problem, find the K closest points to origin using priority queue. We first need to create a function kClosestPoints() that takes three parameters: the array, size, and value K. 
  2. In the function, we will declare a priority queue of pairs which will store the distance and the coordinates of points in the increasing order. 
  3. We will now calculate the distance of every point from the origin, and then we will store the distance and the coordinates of a point in the priority queue.
  4.  After that, we will pick the priority queue’s first K elements, store them in the final array, and then return them.

Code in C++

// C++ code for Find the K closest points to origin using Priority Queue
#include <bits/stdc++.h>
using namespace std;

// function to find the K closest points from the origin
vector<pair<int, int>> kClosestPoints(vector<pair<int, int>> points, int n, int k)
{
    // to store the answer
    vector<pair<int, int>> ans;

   // to store the in an increasing order
    // according to their distance from the origin
    priority_queue<int, vector<pair<int, pair<int, int>>>, greater<pair<int, pair<int, int>>>> p;

    for (int i = 0; i < n; i++)
    {
        // calculating the distance of the point from the origin
        int distance = points[i].first * points[i].first + points[i].second * points[i].second;
        // storing the distance with the point in the priority queue
        p.push({distance, {points[i].first, points[i].second}});
    }

   // taking out the K closest points from the
    // priority queue and storing them
    while (k--)
    {
        auto x = p.top();
        ans.push_back({x.second.first, x.second.second});
        p.pop();
    }
    return ans;
}

// Driver Code
int main()
{

    int k = 3, n = 6;

    vector<pair<int, int>> arr{{-9, -2}, {-10, 1}, {3, -8}, {4, 4}, {-9, 0}, {7, 7}};

    vector<pair<int, int>> ans = kClosestPoints(arr, n, k);
  
    for (int i = 0; i < k; i++)
    {
        cout << "{" << ans[i].first << "," << ans[i].second << "} ";
    }
}

 

Input and Output:

Input: N = 6 , K = 3
[(-9, -2), (-10, 1), (3, 8), (4, 4), (-9, 0), (7, 7)]

Output: {4, 4}, {3, -8}, {-9, 0}

Complexity Analysis

Time Complexity: O(N)

Since we are doing single traversals, therefore, the time complexity is O(N).

Space Complexity: O(N)

Since we store our answer in another array, the space complexity will be O(N).

Frequently asked questions

Q1. What is a heap?

Ans. Heap is a tree-based data structure. More precisely, it is a particular case of a balanced binary tree that stores the tree’s nodes in a specific order. 

Q2. What is a priority queue?

Ans. The priority queue is similar to the regular queue. The only difference is that the priority queue stores elements in a particular order of priority where the top element has the highest priority.

Q3. What is a queue?

Ans. The queue is also a linear data structure, and it is based on the principle of FIFO (First in First Out)

Key takeaways

In this article, we discussed the problem find the k closest points to origin using a priority queue. We have discussed its approach based on the priority queue, and we have also discussed the time and space complexities of the approach.

We hope you have gained a better understanding of the solution to this problem and, now it is your responsibility to solve the problem and try some new and different approaches to this problem. 

Don’t Stop here; try more problems and gain some more expertise in DSA!

  1. Next Greater Element
  2. Least Greater Element
  3. Next Smaller Element
  4. Kth Smallest Element

 

Until then, Keep Learning and Keep Coding.

Was this article helpful ?
0 upvotes

Comments

No comments yet

Be the first to share what you think