text: """973. K Closest Points to Origin
  https://leetcode.com/problems/k-closest-points-to-origin/
  
  We have a list of points on the plane.  Find the K closest points to the
  origin (0, 0).
  
  (Here, the distance between two points on a plane is the Euclidean distance.)
  
  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]]
    (The answer [[-2,4],[3,3]] would also be accepted.)
  
  Note:
    1 <= K <= points.length <= 10000
    -10000 < points[i][0] < 10000
    -10000 < points[i][1] < 10000
  """
  from typing import List
  
  
  class Solution:
      def k_closest(self, points: List[List[int]], k: int) -> List[List[int]]:
          store = {}
          for point in points:
              distance = point[0] ** 2 + point[1] ** 2
              if distance in store:
                  store[distance].append(point)
              else:
                  store[distance] = [point]
          ans = []
          distances = sorted(store.keys())
          for distance in distances:
              for point in store[distance]:
                  if k == 0:
                      return ans
                  ans.append(point)
                  k -= 1
          return ans
  
      def k_closest_2(self, points, k):
          """God damn it!"""
          points.sort(key=lambda point: point[0] ** 2 + point[1] ** 2)
          return points[:k]
  