We are in Beta and we are offering 50% off! Use code BETATESTER at checkout.
You can access a significantly larger sample of the platform's content for free by logging in with your Gmail account. Sign in now to explore.

K Closest Points to Origin (Leetcode 973)

Data Structures and Algorithms Easy Seen in real interview

Given an array of points where points[i] = [xi, yi] represents a point on the X-Y plane and an integer k, return the k closest points to the origin (0, 0).

Examples:

  • Input: [[1, 3], [-2, 2]], k = 2
  • Output:[[-2, 2]] (The distance of [-2,2] from [0,0] is \(\sqrt{8}\) which is less than the distance of [1, 3] \(\sqrt{10}\))


  • Input: [[1, 3], [-2, 2], [5, 6], [7, 8]], k = 2
  • Output: [[-2, 2], [1, 3]]
For this question, we will estimate the Eucledian distance and then use a heap to estimate the k-smaller distances.

import heapq
import math
from typing import List

def kClosest(points: List[List[int]], k: int) -> List[List[int]]:
    d = [(math.sqrt(i**2 + j**2), ind) for ind, (i, j) in enumerate(points)]
    ksmall = heapq.nsmallest(k, d, key=lambda x: x[0])
    return [points[i] for _, i in ksmall]

The time complexity of this solution is \(O(n + k logn)\), as creating a heap takes \(O(log n)\) and we recreating the heap \(k\) times. We can solve this problem through sorting but the time complexity will be \(O(n log n)\). For a nice discussion on this topic, see here.

If we wanted to run it on an example:

inputs = [[1, 3], [-2, 2]]
k=1
print(kClosest(inputs,k))
## [[-2, 2]]


Topics

Heap
Similar questions

Provide feedback