I was solving this question on LeetCode - https://leetcode.com/problems/k-closest-points-to-origin/ I could make two things - 1) We needed to sort the distances of given points in ascending order.
2) We also had to have the point associated with that distance from origin.

After brainstorming, I came up with the idea of using maps from c stl. As they would take care of sorting and also the association of distance and point. My code is as follows -

class Solution 
{
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) 
    {
        map<double,vector<int>> m;
        vector<vector<int>> answer;
        for (int i = 0; i < points.size(); i  )
        {
            double x = sqrt((points[i][0] * points[i][0])   (points[i][1] * points[i][1]));
            m.insert(pair<double, vector<int>>(x,{points[i][0], points[i][1]}));
        }
        
        for (int i = 0; i < k; i  )
        {
            auto it = m.begin();
            advance(it,i);
            answer.push_back(it->second);
        }
        
        return answer;
    }
};

It is working fine for the first 2 testcases and throwing runtime error - stack buffer overflow, I had initially used float for x but I thought because of constraints it was causing the error, so I changed the type to double but still no luck!

It would be a great help if someone can help me figure the mistake here. Thank you in advance!

CodePudding user response：

Let's think of a case where there are two points [-1, 0] and [0, 1], and the value of k is 2. If you use map, you will get only 1 <key, value> pair for your case, because the key (in this case sqrt(1)) is same for both points. So, you need to use multimap, where you can have the same key multiple times. Read here.

The working code example based on your code:

class Solution 
{
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) 
    {
        multimap<int,vector<int>> m;
        vector<vector<int>> answer;
        for (int i = 0; i < points.size(); i  )
        {
            int x = (points[i][0] * points[i][0])   (points[i][1] * points[i][1]);
            m.insert(pair<int, vector<int>>(x,{points[i][0], points[i][1]}));
        }
        int i = 0;
        for (auto it = m.begin(); it != m.end() && i < k; it  , i  ) {
            //cout << it->first << " : " << it->second[0] << ", " << it->second[1] << endl;
            answer.push_back(it->second);
        }
        
        return answer;
    }
};

Suggestions:

• You don't need to bother about whether to store the distance value in double or float. Since you are comparing sqrt(some_value1) with sqrt(some_value2), you can omit the sqrt altogether.
• std::advance has a linear time complexity. You can just simply initialize the iterator at the beginning of the for loop, and increment with operator. This operator has a constant time complexity. Read more about std::advance here.