:orphan:

K Closest Points to Origin
==========================

.. highlight:: none

Problem
-------
https://leetcode.com/problems/k-closest-points-to-origin/

Given an array of ``points`` where ``points[i] = [x``\ :sub:`i`\ ``,
y``\ :sub:`i`\ ``]`` represents a point on the **X-Y** plane and an
integer ``k``, return the ``k`` closest points to the origin
``(0, 0)``.

The distance between two points on the **X-Y** plane is the Euclidean
distance (i.e., ``sqrt(x``\ :sub:`1`\ ``- x``\ :sub:`2`\ ``)``\
:sup:`2`\ ``+ (y``\ :sub:`1`\ ``- y``\ :sub:`2`\ ``)``\
:sup:`2`\ ).

You may return the answer in **any order**. The answer is
**guaranteed** to be **unique** (except for the order that it is in).



**Example 1:**

::

   Input: points = [[1,3],[-2,2]], k = 1
   Output: [[-2,2]]
   Explanation:
   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) < 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]].

**Example 2:**

::

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



**Constraints:**

- ``1 <= k <= points.length <= 10``\ :sup:`4`
- ``-10``\ :sup:`4`\ ``<= x``\ :sub:`i`\ ``, y``\ :sub:`i`\ ``<= 10``\ :sup:`4`

.. highlight:: python

Pattern
-------
Heap, Sorting

Approaches
----------

.. tab-set::

    .. tab-item:: Heap

        **Code**

        .. literalinclude:: ../problems/medium/k-closest-points-to-origin/k_closest_points_to_origin__heap.py
            :language: python
            :lines: 9-

        **Test**

        >>> from k_closest_points_to_origin__heap import kClosest
        >>> kClosest([[1, 3], [-2, 2]], 1)
        [[-2, 2]]
        >>> sorted(kClosest([[3, 3], [5, -1], [-2, 4]], 2))
        [[-2, 4], [3, 3]]

        .. autofunction:: k_closest_points_to_origin__heap.kClosest