Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction
1.1.
Some Examples
2.
Priority Queue Approach
2.1.
Algorithm
2.2.
Code in C++
2.2.1.
Complexity Analysis
3.
Frequently Asked Questions
3.1.
What is a heap?
3.2.
What is a priority queue?
3.3.
What is a queue?
4.
Conclusion
Last Updated: Mar 27, 2024
Medium

Find the K Closest Points to Origin using Priority Queue

gp-icon
Data structures & algorithms (Beginner to Intermediate)
Free guided path
13 chapters
99+ problems
gp-badge
Earn badges and level up
Heap and Priority Queue

Introduction

Priority Queue is an important data structure. It is implemented using Heap Data Structure and has a wide range of applications. It is also important when it comes to technical interviews as well. This blog will discuss the solution to this problem to find the k closest points to the origin using a 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:

  • The Square of Distance of (1, 0) from the origin is 1
  • The Square of Distance of (1, 3) from the origin is 10
  • The Square of Distance of (2, 2) from the origin is 8
  • The 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:

  • The Square of Distance of (2, 1) from the origin is 5
  • The Square of Distance of (-3, -2) from the origin is 13
  • The Square of Distance of (3, 0) from the origin is 9
  • The Square of Distance of (0, -2) from the origin is 4
  • The 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

Also Read, Prefix Sum Array

Priority Queue Approach

To solve this problem, find the K closest points to the origin using the 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 the origin using the 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 that will store the distance and the coordinates of points in 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).

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

Frequently Asked Questions

What is a heap?

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. 

What is a priority queue?

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.

What is a queue?

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

Conclusion

In this article, we discussed the problem find the k closest points to the 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

 

Recommended Readings:


Do check out The Interview guide for Product Based Companies as well as some of the Popular Interview Problems from Top companies like Amazon, Adobe, Google, Uber, Microsoft, etc. on Coding Ninjas Studio.

Also check out some of the Guided Paths on topics such as Data Structure and Algorithms, Competitive Programming, Operating Systems, Computer Networks, DBMS, System Design, Basics of C++, Basics of Java, Basics of Python, etc. as well as some Contests, Test Series, Interview Bundles, and some Interview Experiences curated by top Industry Experts only on Coding Ninjas Studio.

Until then, Keep Learning and Keep Coding.

Previous article
Median of Stream of Integers Problem
Next article
Print All Nodes less than a value X in a Min-Heap
Guided path
Free
gridgp-icon
Data structures & algorithms (Beginner to Intermediate)
13 chapters
109+ Problems
gp-badge
Earn badges and level up
Live masterclass