<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>

class Solution {
public:
    static int squaredDistance(const vector<int>& point) {
        return point[0] * point[0] + point[1] * point[1];
    }

    class compare {
        public:
            bool operator()(const vector<int>& lhs, const vector<int>& rhs) {
                return squaredDistance(lhs) < squaredDistance(rhs);
            }
    };

    vector<vector<int>> kClosest(vector<vector<int>>& points, int k) {
        // T: O(N * logk), S: O(k)
        // priority_queue<pair<int, int>> pq;
        // for (int i = 0; i < points.size(); i++) {
        //     // calculate squared Euclidean distance
        //     int squaredDistance = points[i][0] * points[i][0] + points[i][1] * points[i][1];

        //     // push max heap up to k points
        //     if (pq.size() < k) {
        //         pq.push(make_pair(squaredDistance, i));
        //     // if max heap is full & a closer point is found, 
        //     // pop farthest point and push new point
        //     } else if (squaredDistance < pq.top().first) {
        //         pq.pop();
        //         pq.push(make_pair(squaredDistance, i));
        //     }
        // }

        // // return all points stored in max heap
        // vector<vector<int>> rsf;
        // while (!pq.empty()) {
        //     int idx = pq.top().second;
        //     pq.pop();
        //     rsf.push_back(points[idx]);
        // }

        // return rsf;



        auto cmp = [&](const vector<int>& lhs, const vector<int>& rhs) {
            return squaredDistance(lhs) < squaredDistance(rhs);
        };

        // priority_queue<vector<int>, vector<vector<int>>, decltype(cmp)> pq(cmp);
        // // priority_queue<vector<int>, vector<vector<int>>, compare> pq;
        // for (const auto& point : points) {        
        //     if (pq.size() < k) {
        //         pq.push(point);
        //     } else if (squaredDistance(point) < squaredDistance(pq.top())) {
        //         pq.pop();
        //         pq.push(point);
        //     }
        // }

        // // for (int i = 0; i < points.size(); i++) {
        // //     pq.push(points[i]);

        // //     if (pq.size() > k) {
        // //         pq.pop();
        // //     }
        // // }

        // vector<vector<int>> rsf;
        // while (!pq.empty()) {
        //     rsf.push_back(pq.top());
        //     pq.pop();
        // }

        // return rsf;



        // vector<vector<int>> distances;
        // for (int i = 0; i < points.size(); i++) {
        //     int r = points[i][0] * points[i][0] + points[i][1] * points[i][1];
        //     distances.push_back({r, points[i][0], points[i][1]});
        // }

        // priority_queue<vector<int>, vector<vector<int>>, greater<vector<int>>> pq(distances.begin(), distances.end());

        // vector<vector<int>> rsf;
        // while (k--) {
        //     vector<int> point = pq.top();
        //     pq.pop();
        //     rsf.push_back({point[1], point[2]});
        // }

        // return rsf;


        vector<pair<int, vector<int>>> remaining;
        vector<vector<int>> closest;
        int left = 1;
        int right = 1;

        // for (int i = 0; i < points.size(); i++) {
        //     int SquaredDist = points[i][0] * points[i][0] + points[i][1] * points[i][1];
        //     right = max(right, squaredDist);
        //     remaining.push_back(make_pair(dist, points[i]));
        // }
        for (const auto& point : points) {
            int squaredDist = point[0] * point[0] + point[1] * point[1];
            right = max(right, squaredDist);
            remaining.push_back(make_pair(squaredDist, point));
        }

        while (k) {
            int mid = left + (right - left) / 2;
            // vector<vector<pair<int, vector<int>>>> rsf = split(remaining, distances, mid);
            vector<vector<pair<int, vector<int>>>> rsf = split(remaining, mid);
            vector<pair<int, vector<int>>>& closer = rsf[0];
            vector<pair<int, vector<int>>>& farther = rsf[1];

            if (closer.size() > k) {
                remaining.swap(closer);
                right = mid - 1;
            } else {
                k -= closer.size();
                for (const auto& pair : closer) {
                    closest.push_back(pair.second);
                }
                remaining.swap(farther);
                left = mid + 1;
            }
        }

        return closest;
    }

    vector<vector<pair<int, vector<int>>>> split(vector<pair<int, vector<int>>>& remaining, int mid) {
        vector<vector<pair<int, vector<int>>>> rsf(2);
        vector<pair<int, vector<int>>>& closer = rsf[0];
        vector<pair<int, vector<int>>>& farther = rsf[1];

        for (int i = 0; i < remaining.size(); i++) {
            if (remaining[i].first <= mid) {
                closer.push_back(remaining[i]);
            } else {
                farther.push_back(remaining[i]);
            }
        }

        return rsf;
    }
};
160689