<p>Given an array of <code>points</code> where <code>points[i] = [x<sub>i</sub>, y<sub>i</sub>]</code> represents a point on the <strong>X-Y</strong> plane and an integer <code>k</code>, return the <code>k</code> closest points to the origin <code>(0, 0)</code>.</p>

<p>The distance between two points on the <strong>X-Y</strong> plane is the Euclidean distance (i.e., <code>&radic;(x<sub>1</sub> - x<sub>2</sub>)<sup>2</sup> + (y<sub>1</sub> - y<sub>2</sub>)<sup>2</sup></code>).</p>

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

<p>&nbsp;</p>
<p><strong class="example">Example 1:</strong></p>
<img alt="" src="https://assets.leetcode.com/uploads/2021/03/03/closestplane1.jpg" style="width: 400px; height: 400px;" />
<pre>
<strong>Input:</strong> points = [[1,3],[-2,2]], k = 1
<strong>Output:</strong> [[-2,2]]
<strong>Explanation:</strong>
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]].
</pre>

<p><strong class="example">Example 2:</strong></p>

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

<p>&nbsp;</p>
<p><strong>Constraints:</strong></p>

<ul>
	<li><code>1 &lt;= k &lt;= points.length &lt;= 10<sup>4</sup></code></li>
	<li><code>-10<sup>4</sup> &lt;= x<sub>i</sub>, y<sub>i</sub> &lt;= 10<sup>4</sup></code></li>
</ul>

struct FHelper
{
    int count;
    vector<int> indices;
};

int get_len2(vector<vector<int>>& points, int n)
{
    return points[n][0] * points[n][0] + points[n][1] * points[n][1];
};

class Solution {
public:
    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        vector<FHelper> x_storage(10001);
        vector<FHelper> y_storage(10001);

        for (int i = 0; i < points.size(); ++i)
        {
            x_storage[abs(points[i][0])].count++;
            x_storage[abs(points[i][0])].indices.push_back(i);

            y_storage[abs(points[i][1])].count++;
            y_storage[abs(points[i][1])].indices.push_back(i);
        }

        vector<vector<int>> new_points;
        new_points.reserve(2 * k);
        int counter_x = 0;
        int counter_y = 0;
        unordered_set<int> unique_points;
        
        for (int i = 0; i < 10001; ++i)
        {
            if (counter_x == k)
            {
                break;
            }

            if (x_storage[i].count != 0)
            {
                for (int j = 0; j < x_storage[i].count; ++j)
                {
                    new_points.emplace_back(points[x_storage[i].indices[j]]);
                    counter_x++;
                    unique_points.insert(x_storage[i].indices[j]);
                }
            }
        }

        for (int i = 0; i < 10001; ++i)
        {
            if (counter_y == k)
            {
                break;
            }

            if (y_storage[i].count != 0)
            {
                for (int j = 0; j < y_storage[i].count; ++j)
                {
                    if (unique_points.find(y_storage[i].indices[j]) != unique_points.end())
                    {
                        continue;
                    }

                    new_points.emplace_back(points[y_storage[i].indices[j]]);
                    counter_y++;
                }
            }
        }

        map<int, vector<int>> map;
        int helper = new_points[0][0] * new_points[0][0] + new_points[0][1] * new_points[0][1];

        for (int i = 0; i < k; ++i)
        {
            int len2 = new_points[i][0] * new_points[i][0] + new_points[i][1] * new_points[i][1];
            map[len2].emplace_back(i);
            helper = helper > len2 ? helper : len2;
        }

        for (int i = k; i < new_points.size(); ++i)
        {
            int len2 = new_points[i][0] * new_points[i][0] + new_points[i][1] * new_points[i][1];

            if (helper < len2)
            {
                continue;
            }

            map[len2].emplace_back(i);
        }

        vector<vector<int>> result;

        for (auto it = map.begin(); it != map.end(); ++it)
        {
            for (int j = 0; j < it->second.size(); ++j)
            {
                result.emplace_back(new_points[it->second[j]]);
            }

            k -= it->second.size();

            if ( k <= 0)
            {
                break;
            }
        }

        return result;

    }
};
171316