Given a list of tuples that represent (X, Y) coordinates on an XY plane and an integer K, return a list of the K-closest points to the origin (0, 0).
Input:
points = [[5, 5], [3, 3], [4, 4]], k = 2
Output:
[[3, 3], [4, 4]] or [[4, 4], [3, 3]]
Input:
points = [[-1, 4], [5, 3], [-1, -1], [8, -6], [1, 2]], k = 2
Output:
[[-1, -1], [1, 2]] or [[1, 2], [-1, -1]]
Constraints
The number of nodes in the list is in the range [0, 5000]
K is >= 0 and <= the length of the input list
Reading through the problem a few ideas immediately jump out:
To solve this problem we will need to do some basic algebra. We have a right triangle and we need to calculate the length of the hypotenuse, and we can do so using the Pythagorean theorem:
A^2 + B^2 = C^2
As a quick aside, we don't actually need to calculate C
(the hypotenuse, or distance from origin), as simply calculating A^2 + B^2
for each coordinate will allow us to order the points from closest to furthest from origin without actually determining the exact distance.
Now that we know how to calculate the distances, let's explore different ways to find the k-closest points.
Given we need to find the K
closest points to origin, the naive approach should hopefully become clear relatively quickly. If we calculate the distance for each coordinate pair, we can then sort the coordinates by distance and finally slice the list from 0 to K
in order to return the K
closest points to the origin.
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
# Note: Sorting the input list mutates the input
# -> whether the input should be mutated (as opposed to copied and then sorted)
# -> can be decided collaboratively with the interviewer
points.sort(key=lambda xy_tuple: xy_tuple[0]**2 + xy_tuple[1]**2)
return points[:k]
1def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
2 # Note: Sorting the input list mutates the input
3 # -> whether the input should be mutated (as opposed to copied and then sorted)
4 # -> can be decided collaboratively with the interviewer
5 points.sort(key=lambda xy_tuple: xy_tuple[0]**2 + xy_tuple[1]**2)
6 return points[:k]
O(n * log(n))
O(k)
, as we are sorting in place and returning a new list with K
pointsGiven we have found a somewhat-obvious, naive solution that runs in O(n*log(n))
time, we should start thinking about how we can use different approaches or data structures in order to optimize the time complexity of our algorithm. In order to improve our time complexity we will need to avoid fully sorting the input, and if we aren't sorting the input we will need to repeatedly select the point with the smallest distance from the origin.
It is here that alarm bells should start to go off in our head. What data structure can be used to efficiently, repeatedly select the smallest (or largest) item in a collection? And the answer is... a heap!
To give a quick refresher, heaps are an ordered (but not fully sorted) data structure often backed by an array. They can be created in linear time and they ensure selection of the smallest or largest element at any given time, but they are not fully in order. Read more about how heaps are constructed and used here.
Back to our problem, we can iterate over the list, calculate the distance from the origin for each coordinate and convert it to a heap in place. From there, in order to find the K
closest points to the origin we will need to pop
from the heap K
times, which is often a method exposed via heap library code in a given language.
import heapq
def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
# O(n)
distance_coordinate_tuples = [(x*x + y*y, [x, y]) for x, y in points]
# O(n)
heapq.heapify(distance_coordinate_tuples)
# O(k*log(n))
k_smallest = heapq.nsmallest(k, distance_coordinate_tuples)
# O(k)
return [coordinate for distance, coordinate in k_smallest]
# same as above as a one-liner
def kClosest(self, points, k):
return heapq.nsmallest(k, points, key=lambda p: p[0]**2 + p[1]**2)
1import heapq
2def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
3 # O(n)
4 distance_coordinate_tuples = [(x*x + y*y, [x, y]) for x, y in points]
5 # O(n)
6 heapq.heapify(distance_coordinate_tuples)
7 # O(k*log(n))
8 k_smallest = heapq.nsmallest(k, distance_coordinate_tuples)
9 # O(k)
10 return [coordinate for distance, coordinate in k_smallest]
11# same as above as a one-liner
12def kClosest(self, points, k):
13 return heapq.nsmallest(k, points, key=lambda p: p[0]**2 + p[1]**2)
O(n) + O(k*log(n))
O(1)
(or O(n)
if you mutate the input)Given an array of integers, transform the array in-place to a max heap.
Given the head of a linked list, reverse the list and return the new head.
Given a 32-bit signed integer, reverse digits of the integer.
interviewing.io is a mock interview practice platform. We've hosted over 100K mock interviews, conducted by senior engineers from FAANG & other top companies. We've drawn on data from these interviews to bring you the best interview prep resource on the web.
Interview prep and job hunting are chaos and pain. We can help. Really.