Перейти к содержанию

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:

![https://assets.leetcode.com/uploads/2021/03/03/closestplane1.jpg](https://assets.leetcode.com/uploads/2021/03/03/closestplane1.jpg)

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]
    • Возвращает новый список длины kO(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