K Closest Points to Origin

🇷🇺 Название: K Ближайших точек к началу координат
LeetCode: k-closest-points-to-origin
Временная сложность: O(n log n)
Пространственная сложность: O(k)

Решение

from typing import List  


class Solution:  
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:  
        points.sort(key=lambda p: p[0] ** 2 + p[1] ** 2)  
        return points[:k]

🇺🇸 Условие

Given an array of points where \(points[i] = [x_{i}, y_{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{(x1 - x2)^2 + (y1 - y2)^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.

{
  "examples": [
    {
      "input": {
        "points": [
          [1,3],
          [-2,2]
        ],
        "k": 1
      },
      "output": [
        [-2,2]
      ]
    },
    {
      "input": {
        "points": [
          [3,3],
          [5,-1],
          [-2,4]
        ],
        "k": 2
      },
      "output": [
        [3,3],
        [-2,4]
      ]
    }
  ]
}

Ограничения

• \(1 \leq k \leq points.length \leq 10^4\)
• \(-10^4 \leq x_{i}, y_{i} \leq 10^4\)

Потребление ресурсов

⏱ Time complexity: O(n log n)

• points.sort(...)
  • Сортировка массива из n точек по значению x² + y²
  • В Python list.sort() реализован как Timsort: O(n log n)
  • Каждый вызов key(...) — O(1) (арифметика фиксированная)
  • Всего: O(n log n)
• points[:k]
  • Срез первых k элементов: O(k)

Итог: O(n log n + k) = O(n log n), если k < n

🧠 Space complexity: O(k)

• Сортировка
  • Python использует Timsort, который работает на месте:
    • Никакие копии массива не создаются
    • Только временные буферы → O(log n) максимум (в стеке и сортировке)
  • Но: если points изначально не должен меняться, и ты делаешь sorted(points) — будет O(n) на копию.
• points[:k]
  • Возвращает новый список длины k → O(k)

Итог: O(k + log n) = O(k)

medium array math divide-and-conquer geometry sorting heap-priority-queue quickselect

---

Metadata

• title_rus: K Ближайших точек к началу координат
• difficulty: Medium
• leetcode_url: https://leetcode.com/problems/k-closest-points-to-origin/
• topics: ['Array', 'Math', 'Divide and Conquer', 'Geometry', 'Sorting', 'Heap (Priority Queue)', 'Quickselect']
• time: O(n log n)
• space: O(k)
• grind75: True
• tags: ['Array', 'Divide and Conquer', 'Geometry', 'Heap (Priority Queue)', 'Math', 'Medium', 'Quickselect', 'Sorting', 'problem']
• git_revision_date_localized: 5 июля 2025 г.
• git_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
• git_revision_date_localized_tag:
• git_revision_date_localized_raw_date: 5 июля 2025 г.
• git_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
• git_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
• git_revision_date_localized_raw_iso_date: 2025-07-05
• git_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
• git_revision_date_localized_raw_timeago:
• git_revision_date_localized_raw_custom: 05. июля 2025
• git_site_revision_date_localized_hash: f6ac458ea7f3485fe36c4b8c8f7c610ae2d995e7
• git_site_revision_date_localized_tag:
• git_site_revision_date_localized: 5 июля 2025 г.
• git_site_revision_date_localized_raw_date: 5 июля 2025 г.
• git_site_revision_date_localized_raw_datetime: 5 июля 2025 г. 19:32:08
• git_site_revision_date_localized_raw_datetime-timezone: 5 июля 2025 г. 19:32:08 UTC
• git_site_revision_date_localized_raw_iso_date: 2025-07-05
• git_site_revision_date_localized_raw_iso_datetime: 2025-07-05 19:32:08
• git_site_revision_date_localized_raw_timeago:
• git_site_revision_date_localized_raw_custom: 05. июля 2025