🚶973. K Closest Points To Origin

Medium | Grind 75 | August 30th Tuesday, 2022

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).

The distance between two points on the X-Y plane is the Euclidean distance (i.e., √(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).

Constraints:

• 1 <= k <= points.length <= 10^4

• -104 < xi, yi < 10^4

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.

SOLUTION

1. Create a 2D array to store the distance and the corresponding index of the points list.

2. Iterate over the points list and calculate the distance to the origin for each element.

   1. Append the distance and index of each element to the distance array.

   2. Sort the distance array in ascending order.

3. Iterate over the distance array k times and fetch the elements from the points list using the index value stored in the distance array.

class Solution:
    def kClosest(self, points: List[List[int]], k: int) -> List[List[int]]:
        # store the distance and index from origin for each element in points 
        distance = []
        
        for index, corr in enumerate(points): 
            dist = sqrt(corr[0]**2 + corr[1]**2)
            distance.append([dist, index])
        
        distance.sort()
        
        # store k elements with minimum distance to origin
        result = []
        for i in range(k): 
            result.append(points[distance[i][1]])
        
        return result

TIME AND SPACE COMPLEXITY

TIME: O(nlogn) where n is the length of the points list. We iterate over all the elements once but the runtime of nlogn comes from the sorting we perform on the distance array.

SPACE: O(n) the distance array needs n space to store distance for every element in the points list.